How to solve balancing parentheses problem?


I’m new to dynamic programming and find this problem in http://www.hackerrank.com which is impossible to do I’ve been trying to solve it by 3 days now, the main issue with this problem is that the input string size is in range of 10^9 (creating a dynamic programming 2d array of size 10^9*10^9 takes forever) and no matter what I try the execution time out. someone please help.

the problem : https://www.hackerrank.com/contests/moraxtreme-4-0/challenges/balancing-parentheses-with-a-twist/problem