1111. 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.

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

Problem Summary

A valid parentheses string consists only of "(" and ")" and satisfies one of the following conditions:

• Empty string
• Concatenation, which can be denoted as AB (A concatenated with B), where A and B are both valid parentheses strings
• Nesting, which can be denoted as (A), where A is a valid parentheses string

Similarly, we can define the nesting depth depth(S) of any valid parentheses string s:

• When s is empty, depth("") = 0
• When s is the concatenation of A and B, depth(A + B) = max(depth(A), depth(B)), where A and B are both valid parentheses strings
• When s is nested, depth("(" + A + ")") = 1 + depth(A), where A is a valid parentheses string

For example: "", "()()", and "()(()())" are all valid parentheses strings, with nesting depths of 0, 1, and 2 respectively, while ")(" and "(()" are not valid parentheses strings.

Given a valid parentheses string seq, split it into two disjoint subsequences A and B, such that A and B satisfy the definition of valid parentheses strings (note: A.length + B.length = seq.length).

Now, you need to choose any one group of valid parentheses strings A and B such that the possible value of max(depth(A), depth(B)) is minimized.

Return an answer array answer of length seq.length. The encoding rule for choosing A or B is: if seq[i] is part of A, then answer[i] = 0. Otherwise, answer[i] = 1. Even if multiple valid answers exist, you only need to return one.

Solution Ideas

• Given a parentheses string. Choose the A part and the B part so that the value of max(depth(A), depth(B)) is minimized. Output 0 and 1 in the final array, where 0 indicates the A part and 1 indicates the B part.
• To minimize the value of max(depth(A), depth(B)) in this problem, we can use a greedy idea. If the A part and the B part both match parentheses as early as possible and avoid deep nesting, then the overall depth will become smaller. We only need to arrange the parentheses belonging to A and B alternately among the nested parentheses. For example: "(((())))"; the nesting depth of the above string is 4. According to the greedy idea above, it is marked as 0101 1010.
• This problem can also be solved with a binary splitting idea. Split the depth evenly between the A part and the B part.
  • First traversal: calculate the maximum depth
  • Second traversal: mark parentheses whose depth is less than or equal to half of the maximum depth as 0 (assigned to the A part), otherwise mark them as 1 (assigned to the B part)

Code

package leetcode

// Solution 1: Binary search idea
func maxDepthAfterSplit(seq string) []int {
	stack, maxDepth, res := 0, 0, []int{}
	for _, v := range seq {
		if v == '(' {
			stack++
			maxDepth = max(stack, maxDepth)
		} else {
			stack--
		}
	}
	stack = 0
	for i := 0; i < len(seq); i++ {
		if seq[i] == '(' {
			stack++
			if stack <= maxDepth/2 {
				res = append(res, 0)
			} else {
				res = append(res, 1)
			}
		} else {
			if stack <= maxDepth/2 {
				res = append(res, 0)
			} else {
				res = append(res, 1)
			}
			stack--
		}
	}
	return res
}

// Solution 2: Simulation
func maxDepthAfterSplit1(seq string) []int {
	stack, top, res := make([]int, len(seq)), -1, make([]int, len(seq))
	for i, r := range seq {
		if r == ')' {
			res[i] = res[stack[top]]
			top--
			continue
		}
		top++
		stack[top] = i
		res[i] = top % 2
	}
	return res
}