Maximum Nesting Depth of Two Valid Parentheses Strings

Med

#1051Time: O(N), where N is the length of `seq`. The algorithm iterates through the string twice, so the total time is O(N) + O(N) = O(N).Space: O(N), where N is the length of `seq`. This is because we use an auxiliary array `depths` of size N, in addition to the `answer` array which is also of size N.

Data structures

String Stack

Prompt

A string is a valid parentheses string (denoted VPS) if and only if it consists of "(" and ")" characters only, and:

It is the empty string, or
It can be written as AB (A concatenated with B), where A and B are VPS's, or
It can be written as (A), where A is a VPS.

We can similarly define the nesting depth depth(S) of any VPS S as follows:

depth("") = 0
depth(A + B) = max(depth(A), depth(B)), where A and B are VPS's
depth("(" + A + ")") = 1 + depth(A), where A is a VPS.

For example, "", "()()", and "()(()())" are VPS's (with nesting depths 0, 1, and 2), and ")(" and "(()" are not VPS's.

Given a 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).

Now choose any such A and B such that max(depth(A), depth(B)) is the minimum possible value.

Return an answer array (of length seq.length) that encodes such a choice of A and B: answer[i] = 0 if seq[i] is part of A, else answer[i] = 1. Note that even though multiple answers may exist, you may return any of them.

Example 1:

Input: seq = "(()())"
Output: [0,1,1,1,1,0]

Example 2:

Input: seq = "()(())()"
Output: [0,0,0,1,1,0,1,1]

Constraints:

1 <= seq.size <= 10000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves two separate iterations over the input string. The first pass is dedicated to calculating the nesting depth of each parenthesis. These depths are stored in an auxiliary array. The second pass then uses these stored depths to assign each parenthesis to one of the two subsequences, A or B. The assignment is based on the parity (odd or even) of the character's depth, which effectively balances the nesting depth between the two resulting subsequences.

Algorithm

Create an integer array depths of the same size as seq to store the nesting level of each character.
Initialize a variable currentDepth = 0.
First Pass: Iterate through the input string seq from left to right.
- If the character is '(', we record its depth as the currentDepth and then increment currentDepth for the next level.
- If the character is ')', we first decrement currentDepth (as this parenthesis closes the current level) and then record its depth.
Create an answer array of the same size as seq.
Second Pass: Iterate through the depths array.
- For each character, assign it to group 0 if its depth is even, and group 1 if its depth is odd. This is done by answer[i] = depths[i] % 2.
Return the answer array.

Walkthrough

The core idea is to first determine the nesting level for every parenthesis in the string. A parenthesis's nesting level is defined by how many pairs of parentheses enclose it. We can calculate this by scanning the string and maintaining a depth counter.

Pass 1: Calculate Depths We iterate through the string seq and use a counter currentDepth. When we encounter an opening parenthesis '(', its depth is the current value of currentDepth, and we then increment the counter. When we see a closing parenthesis ')', it closes the current nesting level, so we first decrement the counter and then assign the new value as its depth. The depths are stored in an array, say depths.

Pass 2: Assign Groups After computing all depths, we iterate through the depths array. We assign each parenthesis to a group (0 or 1) based on its depth. A simple and effective strategy is to use the modulo operator: group = depth % 2. This assigns parentheses at depths 0, 2, 4, ... to group 0 and those at depths 1, 3, 5, ... to group 1. This distribution ensures that the maximum depth in either subsequence is minimized.

1class Solution {2    public int[] maxDepthAfterSplit(String seq) {3        int n = seq.length();4        int[] depths = new int[n];5        int[] answer = new int[n];6        int currentDepth = 0;7 8        // Pass 1: Calculate depths for each character9        for (int i = 0; i < n; i++) {10            if (seq.charAt(i) == '(') {11                depths[i] = currentDepth;12                currentDepth++;13            } else { // ')'14                currentDepth--;15                depths[i] = currentDepth;16            }17        }18 19        // Pass 2: Assign groups based on depth parity20        for (int i = 0; i < n; i++) {21            answer[i] = depths[i] % 2;22        }23 24        return answer;25    }26}

Complexity

Time

O(N), where N is the length of `seq`. The algorithm iterates through the string twice, so the total time is O(N) + O(N) = O(N).

Space

O(N), where N is the length of `seq`. This is because we use an auxiliary array `depths` of size N, in addition to the `answer` array which is also of size N.

Trade-offs

Pros

The logic is separated into two distinct, easy-to-understand steps: depth calculation and group assignment.
It correctly solves the problem by minimizing the maximum nesting depth.

Cons

Requires two passes over the input string, making it slightly less performant than a single-pass solution.
Uses extra O(N) space for the depths array, which is not optimal.

This is the most efficient approach, solving the problem in a single pass through the input string. It combines the depth calculation and group assignment steps. By maintaining a running counter for the current nesting depth, it can immediately assign each parenthesis to group 0 or 1 based on the depth's parity. This greedy strategy effectively splits the nested layers of parentheses between the two subsequences, thus ensuring that the maximum depth of either subsequence is as small as possible, which is approximately half of the original string's maximum depth.

Algorithm

Initialize an answer array of the same size as seq.
Initialize a depth counter to 0.
Iterate through the string seq with an index i from 0 to n-1.
For each character c at seq[i]:
- If c is an opening parenthesis '(': a. Assign answer[i] based on the current depth's parity: answer[i] = depth % 2. b. Increment depth.
- If c is a closing parenthesis ')': a. Decrement depth. b. Assign answer[i] based on the new depth's parity: answer[i] = depth % 2.
Return the answer array.

Walkthrough

This approach optimizes the two-pass method by merging the two steps into one. We can calculate the depth and assign the group for each character on the fly.

We iterate through the string seq once, maintaining a depth variable. The key is how we assign the group (0 or 1) based on this depth.

When we encounter an opening parenthesis '(', it belongs to the current nesting level, depth. We assign it to a group based on depth % 2. After the assignment, we increment depth because we are entering a new, deeper nesting level.
When we encounter a closing parenthesis ')', it signifies the end of a nesting level. So, we first decrement depth. This ')' belongs to the level we just exited, which is now represented by the new depth value. We then assign its group based on this new depth % 2.

This method ensures that an opening parenthesis and its corresponding closing parenthesis are assigned to the same group, preserving the structure of a Valid Parentheses String for both subsequences A and B.

1class Solution {2    public int[] maxDepthAfterSplit(String seq) {3        int n = seq.length();4        int[] answer = new int[n];5        int depth = 0;6 7        for (int i = 0; i < n; i++) {8            char c = seq.charAt(i);9            if (c == '(') {10                // Assign based on current depth, then go deeper11                answer[i] = depth % 2;12                depth++;13            } else { // c == ')'14                // Go up a level, then assign based on the level we are now in15                depth--;16                answer[i] = depth % 2;17            }18        }19        return answer;20    }21}

Complexity

Time

O(N), where N is the length of the string `seq`, as we only need to iterate through the string once.

Space

O(N) for the output `answer` array. The auxiliary space complexity is O(1) as we only use a single integer variable (`depth`) to keep track of the state.

Trade-offs

Pros

Highly efficient with an optimal time complexity of O(N).
Space-efficient, using only O(1) auxiliary space (if the output array is not considered).
Simple, elegant, and implemented in a single loop.

Cons

The logic of when to update the depth counter relative to the assignment (depth++ after vs. depth-- before) can be slightly tricky, but any consistent application of the core idea yields a valid optimal solution.

Solutions

Solution

1class Solution {2public3  int[] maxDepthAfterSplit(String seq) {4    int n = seq.length();5    int[] ans = new int[n];6    for (int i = 0, x = 0; i < n; ++i) {7      if (seq.charAt(i) == '(') {8        ans[i] = x++ & 1;9      } else {10        ans[i] = --x & 1;11      }12    }13    return ans;14  }15}

1class Solution {2public:3  vector<int> maxDepthAfterSplit(string seq) {4    int n = seq.size();5    vector<int> ans(n);6    for (int i = 0, x = 0; i < n; ++i) {7      if (seq[i] == '(') {8        ans[i] = x++ & 1;9      } else {10        ans[i] = --x & 1;11      }12    }13    return ans;14  }15};

1class Solution:2    def maxDepthAfterSplit(self, seq: str) -> List[int]: ans = [0] * len(seq) x = 0 for i, c in enumerate(seq): if c == "(": ans[i] = x & 1 x += 1 else: x -= 1 ans[i] = x & 1 return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem