Maximum Nesting Depth of Two Valid Parentheses Strings

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.

Examples

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

Solution

Method 1 – Greedy Alternating Assignment

Intuition

To minimize the maximum nesting depth when splitting the parentheses into two valid strings, we can alternate the assignment of each parenthesis to one of the two groups based on the current depth. This ensures the depths are balanced between the two strings.

Approach

1. Initialize a variable depth to 0 and an answer array.
2. Iterate through the string:
   • For '(': increment depth, assign to group depth % 2.
   • For ')': assign to group depth % 2, then decrement depth.
3. The answer array indicates the group (0 or 1) for each parenthesis.
4. Return the answer array.

Code

C++

class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        vector<int> ans;
        int depth = 0;
        for (char c : seq) {
            if (c == '(') {
                ans.push_back(depth % 2);
                depth++;
            } else {
                depth--;
                ans.push_back(depth % 2);
            }
        }
        return ans;
    }
};

Go

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

Java

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

Kotlin

class Solution {
    fun maxDepthAfterSplit(seq: String): IntArray {
        val ans = IntArray(seq.length)
        var depth = 0
        for (i in seq.indices) {
            if (seq[i] == '(') {
                ans[i] = depth % 2
                depth++
            } else {
                depth--
                ans[i] = depth % 2
            }
        }
        return ans
    }
}

Python

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

Rust

impl Solution {
    pub fn max_depth_after_split(seq: String) -> Vec<i32> {
        let mut ans = Vec::with_capacity(seq.len());
        let mut depth = 0;
        for c in seq.chars() {
            if c == '(' {
                ans.push((depth % 2) as i32);
                depth += 1;
            } else {
                depth -= 1;
                ans.push((depth % 2) as i32);
            }
        }
        ans
    }
}

TypeScript

class Solution {
    maxDepthAfterSplit(seq: string): number[] {
        const ans: number[] = []
        let depth = 0
        for (let i = 0; i < seq.length; ++i) {
            if (seq[i] === '(') {
                ans.push(depth % 2)
                depth++
            } else {
                depth--
                ans.push(depth % 2)
            }
        }
        return ans
    }
}

Complexity

• ⏰ Time complexity: O(n), since we process each character once.
• 🧺 Space complexity: O(n), for the answer array.