Maximum Nesting Depth Of Two Valid Parentheses Strings

Moderate
0/80
Average time to solve is 30m
3 upvotes
Asked in company
Amazon

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )

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.
Sample Input 1 :
2
6
(())()
8
()()(())
Sample Output 1 :
true
true
Explanation of Sample Output 1 :
Test Case 1 :  
Given VPSSEQ = “(())()”. One way to minimize the depth is ‘X’ should contain parentheses at position 1, 3, 5 and 6, and ‘Y’ should contain parentheses at positions 2, 4.
So, X = “()()” and Y = “()”, resulting in the depth of 1, which is minimum. For this the encoded sequence will be “0 1 0 1 0 0”, which will be internally interpreted as correct answer and thus “true” will be printed.

Test Case 2 : 
Given VPSSEQ = “()()(())”. One way to minimize the depth is ‘X’ should contain parentheses at position 1, 2, 3, 4, 5 and 7, and ‘Y’ should contain parentheses at positions 6, 8.
So, X = “()()()” and Y = “()”, resulting in the depth of 1, which is minimum. For this the encoded sequence will be “0 0 0 0 0 1 0 1”, which will be internally interpreted as correct answer and thus “true” will be printed
Sample Input 2 :
2
10
(())((()))
4
(())
Sample Output 2 :
true
true
Hint

Can you divide the parenthesis in ‘X’ and ‘Y’ depending on their depth in the string, ‘VPSSEQ’?

Approaches (3)
Odd/Even Strategy

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.
  • In the end, return ‘RESULT’.
Time Complexity

O(N), where ‘N’ is the length of the string, ‘VPSSEQ’.

 

Since the loop runs ‘N’ times to process every parenthesis.

Space Complexity

O(N), where ‘N’ is the length of the string, ‘VPSSEQ’.

 

We are storing answers in an array so space complexity is O(N).

Code Solution
(100% EXP penalty)
Maximum Nesting Depth Of Two Valid Parentheses Strings
Full screen
Console