A string is given of balanced parentheses(only [ and ]). We want to break this in two subsequences A & B, such that both are balanced and they form the whole string.
How many such breaks are possible for this string.
This can be found here, algorithm - Partitioning a String of Brackets - Stack Overflow
can any one explain solution in detail?
constraint : 1 <= string length <= 1000
This problem can be solved in O(N^2) in the following way:
We will use as DP state the current index and the number of brackets currently opened for the first subsequence: {idx, opened1}. With this information we can uniquely determine how many brackets are currently opened for the second subsequence. At a certain index we know how many brackets have been opened and closed in total. Now opened2 = totOpened - totClosed - opened1. Thus we don’t have to take opened2 in consideration for the DP state. Now at a certain state in our DP, if the current symbol is ‘[’, we can choose to increase opened1 or opened2. Similarly if the symbol is ‘]’ we can choose to decrease opened1 or opened2. The transition is as follows in a top down implementation:
DP[idx][opened1] = DP[idx + 1][opened1 + (S[idx] == '[' ? 1 : -1)] + DP[idx + 1][opened + 1].
If opened1 or opened2 ever becomes negative, the value for this state will be 0.
If we have reached the end of the string, there should be no subsequences with an open bracket in order for them to be valid.
The code is as follows:
1 Like