Counterexample: ()(), For last parenthesis, there are two j’s.
1 Like
Yes and segment [j,i] is balanced as well.
@saurv4u, take j as the largest value such that [j,i] is valid. In this way, you will be able to use dynamic programming approach.
I think you should note that \text{DP[i]} is initialized to 0 in the recurrence and the recurrence is only defined for \text{i} such that there is a balanced expression ending at \text{i}. Also, you never mention that \text{sum(hsh[i], i)} is the sum of the array from \text{hsh[i]} to \text{i}.
Anyway, thank you for the editorial! When I first saw this problem in the Cook-Off, I thought it was really hard, but now I see it wasn’t that bad after all!
I will read your code and will get back to you soon. 
Found the algo problem. Wanted to have [O(1) + stack] extra memory, naive
If you want some test cases, I would recommend to write a function such as this to generate all combinations of input data of size N:
Btw, can only use one type of brackets for this.
char BA[] = { ‘{’, ‘(’, ‘[’, ‘<’, ‘>’, ‘]’, ‘)’, ‘}’ };
void GenSolve(int i)
{
if(i == N)
{
C[i] = ‘\0’;
solve();
return;
}
if(i == 0)
{
for(int k = 0; k < N; ++k)
A[k] = k + 1;
}
for(int b = 0; b < 8; ++b)
{
C[i] = BA[b];
GenSolve(i + 1);
}
}
Alternative approach to dp: represent the string as a list of trees.
The children of each tree are balanced substrings.
Use the maximum subarray sum across each node on its children.
Output the max each time.
You still need the stacks to find where the strings are balanced.
See the code: CodeChef: Practical coding for everyone