Maximum Nesting Depth of Two Valid Parentheses Strings: Depth-Based Splitting

You are given a valid parentheses string seq. You need to split it into two subsequences, A and B, such that both A and B are valid parentheses strings (or empty), and max(depth(A), depth(B)) is minimized. Return an array answer of the same length as seq, where answer[i] is 0 if seq[i] belongs to A and 1 if it belongs to B.

This is LeetCode 1111: Maximum Nesting Depth of Two Valid Parentheses Strings, and it is one of the best examples of how a greedy insight about structure can turn a seemingly complex splitting problem into a single-pass solution.

Why this problem matters

Parentheses nesting is a recurring theme across interview problems. You have probably seen problems about validating parentheses, counting scores, or generating all valid combinations. This problem goes deeper: it asks you to decompose a nested structure into two balanced pieces that share the nesting load as evenly as possible.

The technique it teaches -- splitting based on depth parity -- shows up whenever you need to partition nested or hierarchical structures. It is a beautiful example of how understanding the structure of a problem (nesting depth) leads directly to an optimal strategy, without needing dynamic programming or backtracking.

The key insight

If a string has maximum nesting depth d, the best you can do is split it so that one subsequence handles roughly half the depth and the other handles the rest. The optimal result is ceil(d / 2).

The way to achieve this is surprisingly simple: assign parentheses at even nesting depths to group A and parentheses at odd nesting depths to group B. This interleaving ensures that no single group accumulates more than half the depth.

Why does this work? Think of nesting depth like layers of an onion. Layer 1 wraps layer 2, which wraps layer 3, and so on. If you give every other layer to a different group, neither group ever has two consecutive layers. The maximum depth of either group is at most ceil(d / 2).

The solution

def max_depth_after_split(seq: str) -> list[int]:
    result = []
    depth = 0

    for ch in seq:
        if ch == '(':
            depth += 1
            result.append(depth % 2)
        else:
            result.append(depth % 2)
            depth -= 1

    return result

Let's walk through what each piece does.

We maintain a depth counter that tracks how deeply nested we are at each point. For every opening parenthesis, we increment depth before assigning, because the open paren is entering a new level. For every closing parenthesis, we assign before decrementing, because the close paren is still at its matching open paren's level.

The assignment itself is just depth % 2. When depth is odd, the result is 1 (group B). When depth is even, the result is 0 (group A). That single modulo operation is the entire decision logic.

Notice that we do not need to actually construct the two subsequences or verify they are valid. The depth-parity rule guarantees that matching open and close parens always end up in the same group, which means both subsequences are automatically valid.

Visual walkthrough

Notice how the depth counter rises and falls as we scan left to right. Every time it hits an odd value, we assign to B. Every time it hits an even value, we assign to A. The final result splits the original depth-3 string into group A (max depth 2) and group B (max depth 1), achieving an overall max of 2 -- which is ceil(3 / 2).

Complexity analysis

Time is O(n) where n is the length of the input string. We make a single pass through the string, doing constant work per character.

Space is O(n) for the result array. The depth counter itself is O(1) extra space. If the problem allowed in-place modification (unlikely for this problem format), the auxiliary space would be O(1).

The building blocks

1. Depth tracking with a counter

depth = 0
for ch in seq:
    if ch == '(':
        depth += 1
    else:
        depth -= 1

This is the simplest way to track nesting depth without a full stack. Every ( increases depth by one, every ) decreases it. You will reuse this in problems like "Score of Parentheses," "Minimum Remove to Make Valid Parentheses," and any problem that needs to know "how deep are we right now?"

2. Parity-based assignment

if ch == '(':
    depth += 1
    result.append(depth % 2)
else:
    result.append(depth % 2)
    depth -= 1

The parity trick -- using depth % 2 to alternate between two groups -- is a general strategy for balanced partitioning. Whenever you need to split items into two buckets based on their level in a hierarchy, parity is the first thing to try. The order-of-operations detail (increment before assign for open, assign before decrement for close) is what makes matching pairs land in the same group.

Edge cases

• Empty string: depth never changes, result is an empty array.
• Flat string like ()()(): max depth is 1. Every paren is at depth 1 (odd), so everything goes to B. Group A is empty (depth 0), group B has depth 1. max(0, 1) = 1.
• Deeply nested string like `(((()))): depth goes 1, 2, 3, 4, 4, 3, 2, 1. Parens alternate between A and B, splitting depth 4 into two depth-2 subsequences.
• Already minimal depth: if max depth is 1, you cannot improve beyond 1. The algorithm handles this correctly.
• Odd vs even max depth: when max depth is odd (like 3), the split is ceil(3/2) = 2 and floor(3/2) = 1. When even (like 4), the split is perfectly balanced at 2 and 2.

From understanding to recall

You have seen how depth parity cleanly splits a parentheses string into two balanced subsequences. The logic is just a counter and a modulo -- the code practically writes itself once you know the insight.

But the details that trip people up under pressure are real. Do you increment depth before or after assigning for an open paren? What about for a close paren? If you get the order wrong, matching pairs end up in different groups and the subsequences are invalid. These are not conceptual errors. They are recall errors, and they show up when you have not practiced the pattern enough.

Spaced repetition is how you lock in these details. You write the depth tracker, the parity assignment, and the increment order from memory at increasing intervals. After a few rounds, you do not second-guess the order of operations. You just write it.

Related posts

• Valid Parentheses - The foundational stack problem for matching parentheses
• Score of Parentheses - Uses depth tracking to assign scores to nested parens
• Generate Parentheses - Builds all valid combinations, teaching you how valid strings are structured

CodeBricks breaks this problem into its depth-tracking and parity-assignment building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a parentheses splitting problem appears in your interview, you do not hesitate. You just write it.