LeetCode 1111 - Maximum Nesting Depth of Two Valid Parentheses Strings

LeetCode Problem 1111

Difficulty: 🟡 Medium
Topics: String, Stack

Solution

Problem Understanding

The problem asks us to take a valid parentheses string seq and split it into two disjoint subsequences A and B such that each subsequence is itself a valid parentheses string (VPS). The goal is to assign each character in seq to either A or B in a way that minimizes the maximum nesting depth between the two subsequences.

Input seq is a string containing only '(' and ')' and is guaranteed to be a VPS. The output is an array of integers of the same length as seq, where 0 indicates the character belongs to A and 1 indicates it belongs to B.

Constraints tell us the input can be up to 10,000 characters long. This rules out solutions with time complexity worse than O(n). Edge cases include very shallow VPS strings like "()" and very deep strings like "(((((())))))", as well as strings that are already perfectly balanced in nesting depth.

Approaches

A brute-force approach would attempt all possible ways to partition the parentheses into two VPSs and then compute the depth of each. While this would be correct in principle, it would be infeasible because the number of ways to partition grows exponentially with the length of the string, giving O(2^n) time complexity.

The key insight for an optimal solution is to observe that nesting depth alternates with the level of parentheses. If we track the current depth as we iterate through the string, we can assign parentheses at even depths to A and odd depths to B (or vice versa). This guarantees that each subsequence remains a valid VPS and balances the nesting depth between them.

By splitting based on depth parity, we ensure that neither subsequence ever has more than half of the total nesting at any position, minimizing max(depth(A), depth(B)).

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Enumerate all partitions of seq into VPSs, compute depths, select minimum max depth
Optimal	O(n)	O(n)	Assign parentheses based on current depth parity, track depth incrementally

Algorithm Walkthrough

1. Initialize a variable depth to 0. This will track the current nesting level as we iterate through the sequence.
2. Initialize an empty array answer to hold the assignment of each parenthesis.
3. Iterate through each character c in seq.
4. If c is '(', increment depth by 1. Then assign this '(' to subsequence A if depth % 2 == 1, otherwise to B. Store 0 or 1 in answer accordingly.
5. If c is ')', assign it to the same subsequence as its corresponding '(' using depth % 2, then decrement depth by 1. This ensures the closing parenthesis balances the open one in the same subsequence.
6. Continue until all characters are assigned.
7. Return answer.

Why it works: By alternating assignment based on depth parity, each subsequence receives half of the nesting levels. This guarantees that both A and B remain valid VPSs and that the maximum nesting depth is minimized. The assignments ensure all opens are matched with their closes in the same subsequence.

Python Solution

from typing import List

class Solution:
    def maxDepthAfterSplit(self, seq: str) -> List[int]:
        answer = []
        depth = 0
        for c in seq:
            if c == '(':
                depth += 1
                answer.append(depth % 2)
            else:
                answer.append(depth % 2)
                depth -= 1
        return answer

The Python solution keeps a running depth counter. For each '(', we increment the depth and assign based on parity. For each ')', we assign based on parity first, then decrement. The use of depth % 2 ensures alternating assignment for balanced splitting.

Go Solution

func maxDepthAfterSplit(seq string) []int {
    answer := make([]int, len(seq))
    depth := 0
    for i, c := range seq {
        if c == '(' {
            depth++
            answer[i] = depth % 2
        } else {
            answer[i] = depth % 2
            depth--
        }
    }
    return answer
}

The Go version mirrors the Python logic. A slice answer is preallocated for efficiency. The depth is incremented/decremented and modulo 2 is used for alternating assignment, ensuring minimal maximum nesting depth.

Worked Examples

Example 1: seq = "(()())"

Index	Char	Depth	Assignment	answer
0	'('	1	1 % 2 = 1	1
1	'('	2	2 % 2 = 0	0
2	')'	2	2 % 2 = 0	0
3	'('	2	2 % 2 = 0	0
4	')'	2	2 % 2 = 0	0
5	')'	1	1 % 2 = 1	1

Output: [1,0,0,0,0,1] (equivalent to any valid split with minimal max depth)

Example 2: seq = "()(())()"

Index	Char	Depth	Assignment	answer
0	'('	1	1	1
1	')'	1	1	1
2	'('	1	1	1
3	'('	2	0	0
4	')'	2	0	0
5	')'	1	1	1
6	'('	1	1	1
7	')'	1	1	1

Output: [1,1,1,0,0,1,1,1] (depth-balanced)

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Iterate through each character once, constant time operations
Space	O(n)	Output array of length n, no other significant storage

This complexity is optimal because we must inspect each character at least once, and the output itself is of size n.

Test Cases

# Provided examples
assert Solution().maxDepthAfterSplit("(()())") in ([0,1,1,1,1,0], [1,0,0,0,0,1])
assert Solution().maxDepthAfterSplit("()(())()") in ([0,0,0,1,1,0,1,1], [1,1,1,0,0,1,0,0])

# Edge cases
assert Solution().maxDepthAfterSplit("()") in ([0,0], [1,1])  # minimal VPS
assert Solution().maxDepthAfterSplit("(())") in ([0,1,1,0], [1,0,0,1])  # nested VPS
assert Solution().maxDepthAfterSplit("") == []  # empty string

# Long VPS
assert len(Solution().maxDepthAfterSplit("()"*5000)) == 10000  # max length input

Test	Why
"(()())"	Verifies basic nesting split
"()(())()"	Verifies multiple independent groups
"()"	Minimal VPS, simplest edge
"(())"	Nested VPS, checks alternating assignment
""	Empty string, should return empty array
"()"*5000	Large input, performance and correctness

Edge Cases

One edge case is an empty string. The algorithm correctly returns an empty array because there are no parentheses to assign, maintaining O(1) time behavior.

Another edge case is a deeply nested string such as "((((()))))". Without tracking depth, a naive split might place all parentheses in one subsequence, maximizing nesting unnecessarily. The depth-parity approach balances parentheses across subsequences.

A third edge case is a flat VPS with repeated pairs like "()()()()". Each '(' and ')' pair should alternate between subsequences. Failing to alternate would result in one subsequence taking all pairs and having unnecessary depth. The modulo-based assignment ensures minimal max depth.