Skip to content

1111. Maximum Nesting Depth of Two Valid Parentheses Strings

SourceWeekly Contest 144 Q4DifficultyMediumRating1749

Description

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). The subsequences may not necessarily be contiguous.

For example, for the sequence 123456789, one possible split is:

  • A = {1, 3, 5, 7, 9},

  • B = {2, 4, 6, 8}.

This corresponds to the output [0, 1, 0, 1, 0, 1, 0, 1, 0]  where 0 indicates membership in A and 1 indicates membership in B.

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

Solutions

Solution 1: Greedy

Thinking

Every parenthesis has to be assigned a group, and both groups must stay valid. With \(n \le 10^4\), enumerating the assignment of each position is not realistic. A greedy scan also works: send each '(' to the currently shallower group, and send the matching ')' back with it. That is correct, but the scan has to keep both depths.

Depth grows one nested layer at a time. A chain of depth \(d\) has \(d\) layers, so one group receives at least \(\lceil d/2 \rceil\) of them. Alternating adjacent layers leaves the two groups at depths \(\lceil d/2 \rceil\) and \(\lfloor d/2 \rfloor\).

The group id can just be the parity of the layer, so a single balance \(x\) is enough. A '(' sits on the layer about to be entered, and is labeled by \(x\) before the depth increases. The matching ')' has to follow that same parenthesis, and is labeled by \(x\) after the depth decreases. A pair sees the same parity, and both subsequences stay valid.

We use a variable \(x\) to record the current balance, that is, the number of left parentheses not yet matched. It is also the nesting depth at the current position.

Scan \(\textit{seq}\) from left to right. On a left parenthesis, write the parity of \(x\) into the answer, \(0\) when \(x\) is even and \(1\) when it is odd, then increment \(x\). On a right parenthesis, decrement \(x\) first, then write the parity of the updated value. A matching pair sees the same parity and therefore stays in the same group, so both groups remain valid parentheses strings. If the original nesting depth is \(d\), the larger of the two depths is \(\lceil d/2 \rceil\).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of \(\textit{seq}\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func maxDepthAfterSplit(seq string) []int {
    n := len(seq)
    ans := make([]int, n)
    for i, x := 0, 0; i < n; i++ {
        if seq[i] == '(' {
            ans[i] = x & 1
            x++
        } else {
            x--
            ans[i] = x & 1
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
function maxDepthAfterSplit(seq: string): number[] {
    const n = seq.length;
    const ans: number[] = new Array(n);
    for (let i = 0, x = 0; i < n; ++i) {
        if (seq[i] === '(') {
            ans[i] = x++ & 1;
        } else {
            ans[i] = --x & 1;
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
impl Solution {
    pub fn max_depth_after_split(seq: String) -> Vec<i32> {
        let n = seq.len();
        let mut ans = vec![0; n];
        let mut x = 0;
        for (i, c) in seq.bytes().enumerate() {
            if c == b'(' {
                ans[i] = x & 1;
                x += 1;
            } else {
                x -= 1;
                ans[i] = x & 1;
            }
        }
        ans
    }
}

Comments