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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Nesting Depth of Two Valid Parentheses Strings

Number: 1208

Difficulty: Medium

Paid? No

Companies: Bloomreach

Problem Description

Given a valid parentheses string (VPS), we need to split it into two disjoint subsequences A and B such that both are valid parentheses strings. The goal is to choose the split so that the maximum nesting depth between A and B is minimized. The answer is represented as an array where each index indicates whether a character belongs to A (0) or B (1).

Key Insights

  • The original VPS is balanced; tracking nesting depth helps determine distribution.
  • Assigning parentheses based on the current depth’s parity evenly distributes nested levels.
  • For an opening bracket, use the current depth parity as assignment before incrementing the depth.
  • For a closing bracket, decrement the depth first, then use the updated depth’s parity as assignment.
  • This greedy approach minimizes the maximum depth of either subsequence.

Space and Time Complexity

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

Solution

We use a greedy algorithm with a simple counter (depth) to keep track of the current nesting level. For each character:

  1. If it is an opening bracket ('('), assign it to group (depth % 2) then increment the depth.
  2. If it is a closing bracket (')'), decrement the depth and assign it to group (depth % 2). This ensures that each level of nested parentheses is alternately assigned to the two groups, effectively balancing their nesting depths.

Code Solutions

def maxDepthAfterSplitting(seq):
    # Initialize the result list and depth counter
    result = []
    depth = 0
    # Iterate over each character in the sequence
    for char in seq:
        if char == '(':
            # For an opening bracket, assign group based on current depth
            result.append(depth % 2)
            depth += 1  # Increase nesting level
        else:  # char == ')'
            depth -= 1  # Decrease nesting level first
            result.append(depth % 2)
    return result

# Example usage:
# seq = "(()())"
# print(maxDepthAfterSplitting(seq))
← Back to All Questions