Problem Description

You are given a valid parentheses string (VPS) consisting only of "(" and ")" characters. A VPS is defined as:

• An empty string, or
• A concatenation of two VPS strings AB, or
• A string of the form "(A)" where A is a VPS

The nesting depth of a VPS is defined as:

• depth("") = 0 for an empty string
• depth(A + B) = max(depth(A), depth(B)) for concatenation of two VPS strings
• depth("(" + A + ")") = 1 + depth(A) for a VPS wrapped in parentheses

For example, "" has depth 0, "()()" has depth 1, and "()(()())" has depth 2.

Your task is to split the given VPS seq into two disjoint subsequences A and B such that:

1. Both A and B are valid parentheses strings
2. Every character in seq belongs to either A or B (no character is left out)
3. The maximum depth between A and B is minimized (i.e., max(depth(A), depth(B)) is as small as possible)

Return an array of the same length as seq where:

• answer[i] = 0 if seq[i] belongs to subsequence A
• answer[i] = 1 if seq[i] belongs to subsequence B

The solution uses a greedy approach by tracking the current balance of parentheses with variable x. When encountering an opening parenthesis "(", if x is odd, it's assigned to one group, otherwise to the other. This strategy ensures that consecutive nested parentheses are distributed between the two groups, effectively minimizing the maximum depth.

Intuition

The key insight is understanding what creates depth in a valid parentheses string. Depth increases when we have nested parentheses, like "(())" which has depth 2. The innermost () contributes to the maximum depth.

To minimize the maximum depth when splitting into two subsequences, we need to distribute the nested parentheses between the two groups as evenly as possible. Think of it like this: if we have deeply nested parentheses all going to one group, that group will have high depth. But if we alternate the assignment of nested levels between the two groups, we can roughly halve the maximum depth.

Consider the string "((()))" with depth 3. If we assign all parentheses to group A, it would have depth 3. But if we assign alternating levels to different groups:

• Level 1 (outermost) → Group A: "( )"
• Level 2 (middle) → Group B: " ( ) "
• Level 3 (innermost) → Group A: " () "

This way, Group A gets levels 1 and 3, Group B gets level 2, resulting in both groups having depth 2 instead of 3.

The variable x in the solution tracks our current nesting level. As we encounter an opening "(", we're going deeper (increment x), and when we encounter a closing ")", we're coming back up (decrement x). By using x & 1 (checking if x is odd or even), we alternate the assignment of parentheses at different nesting levels between the two groups.

This greedy strategy ensures that consecutive nesting levels are split between A and B, which optimally minimizes the maximum depth of the resulting subsequences.

Learn more about Stack patterns.

Solution Approach

The implementation uses a greedy algorithm with a simple tracking mechanism to distribute parentheses between two groups.

Algorithm Steps:

1. Initialize the result array: Create an array ans of the same length as the input string seq, initialized with zeros. This array will store our answer where 0 means the character belongs to group A and 1 means it belongs to group B.

2. Track nesting level: Use a variable x initialized to 0 to track the current nesting level as we traverse the string.

3. Process each character: Iterate through each character in seq along with its index:

   • For opening parenthesis "(":
     • First, check if the current level x is odd or even using x & 1 (bitwise AND with 1)
     • Assign the parenthesis to group A (value 0) if x is even, or group B (value 1) if x is odd
     • Increment x to indicate we're going one level deeper
   • For closing parenthesis ")":
     • First, decrement x since we're closing a level
     • Then check if the new level x is odd or even using x & 1
     • Assign the parenthesis to the corresponding group based on the parity

Why this works:

The key insight is that matching parentheses (an opening and its corresponding closing) must be in the same group to maintain validity. By checking the parity of x at the same nesting level for both opening and closing parentheses, we ensure:

• Matching pairs stay together in the same group
• Adjacent nesting levels alternate between groups
• The depth is distributed as evenly as possible

Example walkthrough with "((()))":

• Index 0: "(", x=0 (even) → group A, then x=1
• Index 1: "(", x=1 (odd) → group B, then x=2
• Index 2: "(", x=2 (even) → group A, then x=3
• Index 3: ")", x=3 → decrement to x=2 (even) → group A
• Index 4: ")", x=2 → decrement to x=1 (odd) → group B
• Index 5: ")", x=1 → decrement to x=0 (even) → group A

Result: [0, 1, 0, 0, 1, 0], which splits the string into two valid subsequences with balanced depth.

Example Walkthrough

Let's walk through the solution with the string "(()())":

Initial Setup:

• Input: "(()())"
• Initialize ans = [0, 0, 0, 0, 0, 0] (all zeros initially)
• Initialize x = 0 (tracking nesting level)

Step-by-step Processing:

Index 0: '('

• Current x = 0 (even) → assign to group A (ans[0] = 0)
• Increment x to 1
• State: ans = [0, 0, 0, 0, 0, 0], x = 1

Index 1: '('

• Current x = 1 (odd) → assign to group B (ans[1] = 1)
• Increment x to 2
• State: ans = [0, 1, 0, 0, 0, 0], x = 2

Index 2: ')'

• Decrement x to 1
• Current x = 1 (odd) → assign to group B (ans[2] = 1)
• State: ans = [0, 1, 1, 0, 0, 0], x = 1

Index 3: '('

• Current x = 1 (odd) → assign to group B (ans[3] = 1)
• Increment x to 2
• State: ans = [0, 1, 1, 1, 0, 0], x = 2

Index 4: ')'

• Decrement x to 1
• Current x = 1 (odd) → assign to group B (ans[4] = 1)
• State: ans = [0, 1, 1, 1, 1, 0], x = 1

Index 5: ')'

• Decrement x to 0
• Current x = 0 (even) → assign to group A (ans[5] = 0)
• State: ans = [0, 1, 1, 1, 1, 0], x = 0

Final Result: [0, 1, 1, 1, 1, 0]

Verification:

• Group A (indices with 0): positions 0 and 5 → "( )" → valid with depth 1
• Group B (indices with 1): positions 1,2,3,4 → " ()() " → valid with depth 1

Both subsequences are valid and have depth 1, which is optimal for this string (original depth was 2).

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string seq. The algorithm iterates through each character in the string exactly once using a single for loop with enumerate, performing constant-time operations (comparison, bitwise AND operation & 1, increment/decrement, and array assignment) for each character.

The space complexity is O(n) for the output array ans which stores the result. However, if we exclude the space required for the output (as is common practice when analyzing space complexity for problems that require returning a result), the space complexity is O(1). The algorithm only uses a constant amount of extra space: the variable x to track the depth, and the loop variables i and c.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Order of Operations for Closing Parentheses

The Problem: A common mistake is to check the parity of depth (or x) before decrementing it when processing a closing parenthesis. This would look like:

if char == ")":
    result[index] = depth & 1  # WRONG: checking before decrementing
    depth -= 1

This breaks the algorithm because matching parentheses won't be assigned to the same group. The closing parenthesis would be checking the parity at a different nesting level than its corresponding opening parenthesis.

The Solution: Always decrement depth first for closing parentheses, then check the parity:

if char == ")":
    depth -= 1  # CORRECT: decrement first
    result[index] = depth & 1  # then check parity

Pitfall 2: Incorrect Order for Opening Parentheses

The Problem: Similarly, incrementing depth before checking parity for opening parentheses:

if char == "(":
    depth += 1  # WRONG: incrementing before checking
    result[index] = depth & 1

This would cause the opening parenthesis to be assigned based on the wrong nesting level.

The Solution: Check parity first, then increment for opening parentheses:

if char == "(":
    result[index] = depth & 1  # CORRECT: check first
    depth += 1  # then increment

Pitfall 3: Using Modulo Instead of Bitwise AND

The Problem: Using depth % 2 instead of depth & 1:

result[index] = depth % 2  # Works but less efficient

While this is functionally correct, it's less efficient than bitwise operations.

The Solution: Use bitwise AND for better performance:

result[index] = depth & 1  # More efficient

Example Demonstrating the First Pitfall

Consider the string "(())"

Incorrect approach (checking before modifying depth for closing parentheses):

• Index 0: "(", depth=0 → group 0, depth becomes 1
• Index 1: "(", depth=1 → group 1, depth becomes 2
• Index 2: ")", depth=2 → group 0 (WRONG!), depth becomes 1
• Index 3: ")", depth=1 → group 1 (WRONG!), depth becomes 0

Result: [0, 1, 0, 1] - This splits into "()" (group 0) and "()" (group 1), but the second pair is invalid!

Correct approach:

• Index 0: "(", depth=0 → group 0, depth becomes 1
• Index 1: "(", depth=1 → group 1, depth becomes 2
• Index 2: ")", depth becomes 1 → group 1 (matches with index 1)
• Index 3: ")", depth becomes 0 → group 0 (matches with index 0)

Result: [0, 1, 1, 0] - This correctly maintains matching pairs.