I have read the editorial but didn’t understand the proof. Can someone please explain the proof!
Go through this comment. His approach is the best.
I dont know if it helps,but u could try it with dp.
dp[i][j] denotes whether it is possible to have a valid substring ending at i of length j.
dp[i][0]=true for all i
Lets talk about recurrence:
if(s[i]==’)’ or s[i]==’?’):
then u can end with this i,now s[i-1] may be ‘(’ or ‘)’.
case 1: ‘(’
so we have a string like this validStringEndAti-2 ( )
So in this case dp[i][j]=dp[i-2][j-2]
case 2: ‘)’
So we have string like this validString ( ValidStringEndingWith) )
eg ()(()),()()(())
So in this case we see all possible lengths of i-1,and go to those position lets say x and see if s[x-1]==’(’,if it is then dp[i][j]=dp[i][j] or dp[x-2][j-(x-2)] (as now we can concatenate the strings ending at x-2)
(This would probably time out so u could try using some data structures or bit manipulation)