1111. Maximum Nesting Depth of Two Valid Parentheses Strings

1. Description

A balanced parentheses string contains only ‘(’ and ‘)’. Every prefix has at least as many opening parentheses as closing ones, and the total counts are equal. The empty string is also balanced.
Its nesting depth is the largest number of simultaneously unmatched opening parentheses; an empty string has depth 0.

Given a balanced string seq, assign every character to one of two subsequences A and B, preserving the original order within each subsequence. Both subsequences must remain balanced, and either may be empty.
Minimize the larger of their nesting depths.
Return an array answer with one entry per character: use 0 for membership in A and 1 for membership in B. Any optimal assignment is acceptable.

2. Example

Example 1

Input: seq = “(()())”
Output: [0,1,1,1,1,0]
Explanation: A = “()” and B = “()()”, so both depths are 1.

Example 2

Input: seq = “()(())()”
Output: [0,0,0,1,1,0,1,1]
Explanation: A = “()()” and B = “()()”, again achieving a maximum depth of 1.

3. Constraints

• 1 <= seq.length <= 10$^4$
• seq contains balanced parentheses only.

4. Solutions

Greedy

n = seq.size()
Time complexity: O(n)
Space complexity: O(1), excluding the output array

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<int> maxDepthAfterSplit(const string &seq) {
        const int n = seq.size();
        vector<int> answer(n);

        int depth = 0;
        for (int i = 0; i < n; ++i) {
            if (seq[i] == '(') {
                ++depth;
                answer[i] = depth % 2;
            } else {
                answer[i] = depth % 2;
                --depth;
            }
        }

        return answer;
    }
};