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.
Explanation:
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.
(1)
The description of the problem contains the following sentence:
‘It is also guaranteed that A is a valid parentheses sequence.’.
One of the constraints is:
1 ≤ |A| ≤ 100000(105)
so a test case can be ‘(’ or ‘)’ but none of these sequences is valid.
(2)
The description of the problem contains the following sentence:
‘If there are several such strings with the minimal possible length, then Mike will choose the least one lexicographically, considering ‘(’ to be less than ‘)’.’
Is it possible to construct two strings with the minimum possible length? I don’t think so. Why the above information is present in the description?
You are calling strlen function for each iteration in the loop. Which is unnecessory. It is sufficient to calculate the length just once. Change that line to :
int len=strlen (str);
for (ll i=0; i <len; i++)
Also change size of string s to 100001 to accommodate the ‘\0’
Ya exactly !
bcoz the string length needs to be minimum then we can print just that single
desired type of string as mentioned in editorial
the setter’s more mechanical i guess
imposing uneccessary condition can confuse pro programmers as well!