Stack Title: nesting depth of valid parentheses

subject

Title and provenance

title ： Nesting depth of valid parentheses

Source ：1111. Nesting depth of valid parentheses

difficulty

6 level

Title Description

requirement

A string is a valid bracket string , If and only if the string contains only $\text{"("}$ and $\text{")"}$, And meet one of the following conditions ：

• The string is an empty string ;
• The string can be written as $\text{AB}$（$\text{A}$ And $\text{B}$ String connection ）, among $\text{A}$ and $\text{B}$ Are valid bracket strings ;
• The string can be written as $\text{(A)}$, among $\text{A}$ Is a valid parenthesis string .

For valid bracket strings $\text{S}$, Its nesting depth $\text{depth(S)}$ The definition is as follows ：

• $\text{depth("")}=0$;
• $\text{depth(A + B) = max(depth(A), depth(B))}$, among $\text{A}$ and $\text{B}$ Are valid bracket strings ;
• $\text{depth("(" + A + ")") = 1 + depth(A)}$, among $\text{A}$ Is a valid parenthesis string .

for example ,$\text{""}$、$\text{"()()"}$ and $\text{"()(()())"}$ Is a valid bracket string （ The nesting depth is $\text{0}$、$\text{1}$ and $\text{2}$）,$\text{")("}$ and $\text{"(()"}$ Is not a valid parenthesis string .

Given a valid bracket string $\text{seq}$, Divide it into two disjoint subsequences $\text{A}$ and $\text{B}$, bring $\text{A}$ and $\text{B}$ Is a valid bracket string , And $\text{A.length + B.length = seq.length}$.

Choose any $\text{A}$ and $\text{B}$ bring $\text{max(depth(A), depth(B))}$ The minimum value of .

Returns an array of $\text{answer}$（ The length is $\text{seq.length}$）, Express choice $\text{A}$ and $\text{B}$ The coding ： If $\text{seq[i]}$ among $\text{A}$ be $\text{answer[i] = 0}$, otherwise $\text{answer[i] = 1}$. If there are multiple answers that meet the requirements , Just return any one of them .

Example

Example 1：

Input ：$\text{seq = "(()())"}$
Output ：$\text{[0,1,1,1,1,0]}$

Example 2：

Input ：$\text{seq = "()(())()"}$
Output ：$\text{[0,0,0,1,1,0,1,1]}$

Data range

• $\text{1}\le \text{seq.size}\le \text{10000}$

solution

Ideas and algorithms

Before considering dividing the valid bracket string into two disjoint subsequences , First, we need to consider the nesting depth of each bracket . Valid parenthesis string , Each left parenthesis has a matching right parenthesis , The nesting depth of a pair of matching left and right parentheses is the same .

To calculate the nesting depth of each bracket , You can use the stack to store the left parenthesis , Get the nesting depth according to the number of elements in the stack . Traverse valid bracket strings from left to right $\text{seq}$, If the left bracket is encountered, the left bracket is put on the stack , If the right bracket is encountered, the left bracket at the top of the stack will be out of the stack , Indicates that the current right bracket matches the left bracket at the top of the stack . According to the definition of nesting depth , The nesting depth of the left bracket and the right bracket are calculated as follows ：

• For the left bracket , The number of elements in the stack after the stack operation is the nesting depth of the left bracket ;

• For the right bracket , The number of elements in the stack before the stack operation is the nesting depth of the right bracket .

After clarifying the calculation method of the nesting depth of brackets , Go back to the original question , Put valid parenthesis strings $\text{seq}$ Divided into two disjoint subsequences $A$ and $B$, Minimize the nesting depth of two subsequences . As long as the half bracket in the stack belongs to the subsequence $A$, The other half of the parentheses belong to the subsequence $B$, It can satisfy the minimum nesting depth of two subsequences . In terms of implementation , Divide the brackets of odd layers to $A$, Assign brackets of even layers to $B$ that will do .

Because the nesting depth of a pair of matching left and right parentheses is the same , Therefore, a pair of matching left and right parentheses must be in the same subsequence . Thus we can see that , The number of left and right parentheses in any subsequence must be equal , And the left bracket must appear before the matching right bracket , Therefore, both subsequences are valid parenthesis strings .

Because only the left parenthesis is stored in the stack , Therefore, there is no need to really maintain a stack , Just record the nesting depth in the traversal process .

Code

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

Complexity analysis

• Time complexity ：$O(n)$, among $n$ Is string $\text{seq}$ The length of . Need to traverse the string $\text{seq}$ once , Each time the nesting depth is updated $O(1)$.

• Spatial complexity ：$O(1)$. In addition to the return value , The space complexity used is constant .