Given a valid parentheses sequence A. Your task is to find another valid parentheses sequence B with the minimal possible length, such that the maximal balance over all prefixes of A is equal to the same characteristic of B.
This problem requires some logical thinking and being familiar with valid parentheses sequences.
Let’s consider a pseudocode that has been provided to you in the statement:
FUNCTION F( S - a valid parentheses sequence ) BEGIN balance = 0 maxbalance = 0 FOR index FROM 1 TO LENGTH(S) BEGIN if S[index] == '(' then balance = balance + 1 if S[index] == ')' then balance = balance - 1 maxbalance = max( maxbalance, balance ) END RETURN maxbalance END
The first observation is that there should be at least maxbalance open brackets in B. Every open bracket should also have a paired closed bracket, so the length of B is at least 2 * maxbalance. Fortunartely, there’s a valid B with the length equal to 2 * maxbalance, it looks like this: the first maxbalance brackets are open brackets, the last max_balance brackets are closed ones. It isn’t hard to prove that this is the only way to construct B with such a length.
So, here are the keypoints of the solution:
- Determing the value of maxbalance;
- B is maxbalance open brackets and maxbalance closed brackets concatenated together.
Complexity is O(N) per a testcase.
Please, check out Setter’s and Tester’s solutions for your better understanding.
Setter’s Solution: link
Tester’s Solution: link