How to solve balancing parentheses problem?

I’m new to dynamic programming and find this problem in 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 :