Last Updated: 12 Apr, 2021
Maximum Nesting Depth Of Two Valid Parentheses Strings
Moderate
Asked in company
You are given a valid parentheses string (VPS), ‘VPSSEQ’. You have to minimize the depth of a VPS by splitting all pairs of parentheses into two disjoint subsequences, ‘X’ and ‘Y’, such that ‘X’ and ‘Y’ are VPS's and length of ‘X’ + length of ‘Y’ = length of ‘VPSSEQ’.
Your task is to return an array, ’result’ (of size ‘VPSSEQ.length’) that encodes such a choice of ‘X’ and ‘Y’: if ‘VPSSEQ[ i ]’ is part of ‘X’, RESULT[ i ] = 0, else RESULT[ i ] = 1.
Note :
1) A valid parentheses string (VPS) is a string containing balanced parentheses, i.e. an opening parenthesis is followed by exactly one closing parenthesis, and any closing parenthesis is preceded by at least one unbalanced opening parenthesis.
For example, “(())()”, “”, “()(())()((()))(())” are VPS whereas “(()”, “)()(”, “((” are not VPS.
2) The nesting depth of any VPS is defined as follows:
2.1) depth("") = 0.
2.2) depth(X + Y) = max(depth(X), depth(Y)), where ‘X’ and ‘Y’ are VPS's.
2.3) depth("(" + X + ")") = 1 + depth(X), where ‘X’ is a VPS.
3) Given VPSSEQ= "(())()" can be split in two disjoint VPS sequences in a number of ways. Like, X = "(())()" and Y = "”, X = “(())” and Y = “()”, X = “()” and Y = “()()”, etc. Out of all, X = “()” and Y = “()()” will have minimum depth of 1.
4) A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Input Format :
The first line of input contains an integer 'T' representing the number of test cases.
The first line of each test case contains an integer ‘N’ representing the length of the string ‘VPSSEQ’.
The last line of each test case contains a string of parenthesis, ‘VPSSEQ’ of length ‘N’.
Output Format :
For each test case, return an array, ’RESULT’ (of size ‘VPSSEQ.length’) that encodes such a choice of ‘X’ and ‘Y’: if ‘VPSSEQ[ i ]’ is part of ‘X’, RESULT[ i ] = 0, else RESULT[ i ] = 1.
Since multiple answers may exist, you may return any of them. The encoded sequence will be internally interpreted and if correct then ‘true’ will be printed otherwise ‘false’ will be printed.
The output of each test case will be printed in a separate line.
Constraints :
1 <= T <= 5
1 <= N <= 5000
VPSSEQ[ i ] ∈ { ‘(‘, ‘)’}
‘VPSSEQ’ is a VPS.
Where ‘VPSSEQ’, and ‘VPSSEQ[ i ]’ is the ‘i’th element in the ‘VPSSEQ’ string.
Time limit: 1 sec
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Approaches
Since all parentheses can be split into two groups, the minimum achievable depth will always be ‘ceil(MAXDEPTH / 2)’ that can be achieved by putting one half in each group.
So we effectively need to cut any string in half while making sure that the resulting half-strings are VPS.
The idea is to use the odd/even strategy. We will find the depth at every index of the string and then put all odd-depth parentheses in one group and all even-depth parentheses in the other. The depth will increase as we go deeper into the string and vice versa.
For example:
VPSSEQ = “( ( ( ( ( ) ) ) ) )”
DEPTH: 1 2 3 4 5 5 4 3 2 1
Since depth(VPSSEQ) = 5, minimum achievable depth = ceil(5/2) = 3.
With odd/even strategy, we will put all odd depth parentheses in ‘X’ and even depth parentheses in ‘Y’. So, X = “((()))” and Y = “(())”
Also, depth(VPSSEQ) = depth(X + Y) = max(depth(X), depth(Y) = max(3, 2) = 3.
So, the ‘X’ and ‘Y’ thus obtained are valid.
Assign ‘0’ for parenthesis in ‘X’ and ‘1’ for parenthesis in ‘Y’. Thus, the ‘result’ = {0, 1, 0, 1, 0, 0, 1, 0, 1, 0}.
Algorithm:
- Declare a vector of integers, ‘RESULT’ to store the sequence of 0s and 1s for the output.
- Declare an integer variable, ‘CURRENTDEPTH’ that assigns depth for each parenthesis.
- Run a loop for every character, ‘CH’ in the ‘VPSSEQ’.
- If CH == ‘(‘, that shows that we are going deeper in the string. So, we will
- Increment the ‘CURRENTDEPTH’ by 1.
- Push ‘CURRENTDEPTH % 2’ in the ‘RESULT’.
- Else, we are coming out of the depth. So, we will
- Push ‘CURRENTDEPTH% 2’ in the ‘RESULT’.
- Decrement ‘CURRENTDEPTH’ by 1.
- If CH == ‘(‘, that shows that we are going deeper in the string. So, we will
- In the end, return ‘RESULT’.
We have seen in Approach 1 that the minimum achievable depth will always be ceil(MAXDEPTH / 2). So, instead of splitting the string using odd/even strategy, we can use current depth as the criterion for splitting.
For this purpose, first, we will find the depth of the complete string, say: ‘TOTALDEPTH’. Now, parentheses at the depth greater than ‘TOTALDEPTH / 2’ will be placed in ‘X’ and parentheses at the depth less than ‘TOTALDEPTH / 2’ will be placed in ‘Y’.
Algorithm:
- Declare a vector of integers, ‘RESULT’ to store the sequence of 0s and 1s for the output.
- Call ‘findDepth’ function and pass ‘VPSSEQ’ to find the depth of the complete string. Store the returned value in an integer variable, ‘TOTALDEPTH’.
- Declare an integer variable, ‘CURRENTDEPTH’ that will keep track of the current depth of the parenthesis present in ‘VPSSEQ’.
- Run a loop for every character, ‘CH’ in the ‘VPSSEQ’.
- If CH == ‘(‘ that shows that we are going deeper in the string. So, we will
- Increment the ‘CURRENTDEPTH’ by 1.
- If CURRENTDEPTH > TOTALDEPTH / 2, then we will put it in ‘X’. So,
- Push 0 in the ‘RESULT’.
- Else, we will put it in ‘Y’. So,
- Push 1 in the ‘RESULT’.
- Else, we are coming out of the depth. So, we will check
- If CURRENTDEPTH > TOTALDEPTH / 2, then we will put it in ‘X’. So,
- Push 0 in the ‘RESULT’
- Else, we will put it in ‘Y’. So,
- Push 1 in the ‘RESULT’.
- Decrement the ‘CURRENTDEPTH’ by 1.
- If CURRENTDEPTH > TOTALDEPTH / 2, then we will put it in ‘X’. So,
- If CH == ‘(‘ that shows that we are going deeper in the string. So, we will
- In the end, return ‘RESULT’.
Description of ‘findDepth’ function
This function will take one parameter :
- STR: A string of which depth has to be calculated.
int findDepth(STR):
- Declare two integer variables, ‘TOTALDEPTH’ and ‘CURRENTDEPTH’. Initialize both of them by 0.
- Run a loop for every character, ‘CH’ in the ‘STR’.
- If CH == ‘(‘ that shows that we are going deeper in the string. So, we will
- Increment the ‘CURRENTDEPTH’ by 1.
- Else, we are coming out of the depth. So, we will
- Decrement the ‘CURRENTDEPTH’ by 1.
- Store the maximum of ‘TOTALDEPTH’ and ‘CURRENTDEPTH’ in ‘TOTALDEPTH’.
- In the end, return ‘TOTALDEPTH’.
The idea is to use the greedy approach to solve the problem. We can scan the string, ‘VPSSEQ’ from left to right (to ensure that order is maintained). When we process an opening parenthesis, we will allocate it to the subsequence with less number of the unmatched opening parenthesis. And, when we will process a closing parenthesis, we will allocate it to the subsequence with more number of the unmatched closing parenthesis.
Algorithm:
- Declare a vector of integers, ‘RESULT’ to store the sequence of 0s and 1s for the output.
- Declare two integer variables, ‘X’ and ‘Y’. Initialize both of them by 0.
- Run a loop for every character, ‘CH’ in the ‘VPSSEQ’.
- If CH == ‘(‘, we will check:
- If X <= Y, that shows ‘X’ has less number of the unmatched opening parenthesis. So, we will
- Push 0 in the ‘RESULT’.
- Increment ‘X’ by 1.
- Else, we will
- Push 1 in the ‘RESULT’.
- Increment ‘Y’ by 1.
- If X <= Y, that shows ‘X’ has less number of the unmatched opening parenthesis. So, we will
- Else we will check
- If X >= Y, that shows ‘X’ has more number of the unmatched opening parenthesis. So, we will
- Push 0 in the ‘RESULT’.
- Increment ‘X’ by 1.
- Else, we will
- Push 1 in the ‘RESULT’.
- Increment ‘Y’ by 1.
- If X >= Y, that shows ‘X’ has more number of the unmatched opening parenthesis. So, we will
- If CH == ‘(‘, we will check:
- In the end, return ‘RESULT’.