# Maximum Nesting Depth of Two Valid Parentheses Strings
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings)
Canonical: https://scaleengineer.com/dsa/problems/maximum-nesting-depth-of-two-valid-parentheses-strings
**Data structures:** String, Stack
---
## Problem
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
## Two-Pass Approach using Depth Calculation
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int n = seq.length();
        int[] depths = new int[n];
        int[] answer = new int[n];
        int currentDepth = 0;

        // Pass 1: Calculate depths for each character
        for (int i = 0; i < n; i++) {
            if (seq.charAt(i) == '(') {
                depths[i] = currentDepth;
                currentDepth++;
            } else { // ')'
                currentDepth--;
                depths[i] = currentDepth;
            }
        }

        // Pass 2: Assign groups based on depth parity
        for (int i = 0; i < n; i++) {
            answer[i] = depths[i] % 2;
        }

        return answer;
    }
}
```
### Algorithm
1. Create an integer array `depths` of the same size as `seq` to store the nesting level of each character.
2. Initialize a variable `currentDepth = 0`.
3. **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.
4. Create an `answer` array of the same size as `seq`.
5. **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`.
6. Return the `answer` array.

## Single-Pass Greedy Approach
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.
**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.
**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.
### Explanation
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`.

```java
class Solution {
    public int[] maxDepthAfterSplit(String seq) {
        int n = seq.length();
        int[] answer = new int[n];
        int depth = 0;

        for (int i = 0; i < n; i++) {
            char c = seq.charAt(i);
            if (c == '(') {
                // Assign based on current depth, then go deeper
                answer[i] = depth % 2;
                depth++;
            } else { // c == ')'
                // Go up a level, then assign based on the level we are now in
                depth--;
                answer[i] = depth % 2;
            }
        }
        return answer;
    }
}
```
### Algorithm
1. Initialize an `answer` array of the same size as `seq`.
2. Initialize a `depth` counter to 0.
3. Iterate through the string `seq` with an index `i` from 0 to `n-1`.
4. 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`.
5. Return the `answer` array.

# Solutions
### Java

```java
class Solution {
public
  int[] maxDepthAfterSplit(String seq) {
    int n = seq.length();
    int[] ans = new int[n];
    for (int i = 0, x = 0; i < n; ++i) {
      if (seq.charAt(i) == '(') {
        ans[i] = x++ & 1;
      } else {
        ans[i] = --x & 1;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> maxDepthAfterSplit(string seq) {
    int n = seq.size();
    vector<int> ans(n);
    for (int i = 0, x = 0; i < n; ++i) {
      if (seq[i] == '(') {
        ans[i] = x++ & 1;
      } else {
        ans[i] = --x & 1;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```