We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Nesting Depth of Two Valid Parentheses Strings

Difficulty: Medium

Problem Description

Given a valid parentheses string (VPS) seq, split it into two disjoint subsequences A and B, such that A and B are VPS's (and A.length + B.length = seq.length). The goal is to choose A and B such that max(depth(A), depth(B)) is minimized. Return an answer array encoding the choice of A and B: answer[i] = 0 if seq[i] is part of A, else answer[i] = 1.

Key Insights

  • A valid parentheses string can be broken down into subsequences while maintaining their validity.
  • The nesting depth of a VPS can be computed by tracking the balance of opening and closing parentheses.
  • To minimize the maximum depth of the two subsequences, we can alternate between assigning parentheses to A and B.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the input string. Space Complexity: O(n) - for the output array.

Solution

To solve the problem, we can utilize a simple greedy approach. We will iterate through the characters of the string seq while maintaining a balance of open parentheses. For every opening parenthesis (, we will assign it to one of the subsequences (A or B) based on the current balance, and for every closing parenthesis ), we will assign it to the other subsequence. This way, we can ensure that the depths of both subsequences are as balanced as possible.

Code Solutions

def maxDepthAfterSplit(seq: str):
    answer = []
    # Balance variable to keep track of the depth
    balance = 0
    
    for char in seq:
        if char == '(':
            # Increase balance for opening parenthesis
            balance += 1
            # Assign to A if balance is odd, else to B
            answer.append(balance % 2)
        else:
            # Assign to A if balance is odd, else to B
            answer.append((balance - 1) % 2)
            # Decrease balance for closing parenthesis
            balance -= 1
            
    return answer
← Back to All Questions