Maximum Nesting Depth of Two Valid Parentheses Strings — Editorial

Opening the reading…

Intuitionthe deepest active pairs can be shared between two groups

At any position, the current depth tells you how many opening parentheses are active. When you read an opening parenthesis, depth increases before that parenthesis becomes part of a pair; when you read a closing parenthesis, it closes the pair currently sitting at the top of the nesting structure. The key is to distribute these active levels between the two groups instead of assigning whole substrings.

Assign depth 1 to one group, depth 2 to the other, depth 3 back to the first, and so on. A closing parenthesis must receive the same group as the opening parenthesis it closes, so use the current depth before decreasing it. Each group's active pairs then occupy alternating levels, making its deepest nesting roughly half of the original depth.

Alternating active nesting levels divides one deep chain between the two groups.

This balance is optimal, not just convenient. If the original string reaches depth D, then D pairs are active at that moment. Two groups must share those D pairs, so one group has at least ceil(D / 2) of them and no answer can have a smaller maximum depth. The alternating assignment gives each group at most ceil(D / 2), meeting that lower bound.

Approach

Create an answer array with one group value for every character, because the judge needs the assignment at the original indices rather than the two subsequences themselves.

Start depth at zero, because it represents the number of unmatched opening parentheses before the current character.

When the character is '(', increment depth first and assign depth % 2. The new depth is the level of this opening parenthesis; assigning from the old depth would shift every pair to the wrong group.

When the character is ')', assign depth % 2 before decrementing it. The current depth identifies the opening parenthesis being closed, so both ends of a pair enter the same subsequence.

Return the assignments after one left-to-right scan. Every pair is assigned consistently, and the parity split keeps each group's maximum nesting depth within the optimal bound.

Complexityone scan and constant working state

MEASURE	BOUND	WHY
Time	O(n)	The loop examines each of the n characters once, performs constant-time arithmetic and assignment, and never revisits a character.
Space	O(1) extra	The answer array uses O(n) space, but it is required output and is excluded from the extra-space bound. Beyond that array, the algorithm stores only depth and the loop state, so the working space stays constant even for the worst valid nesting shape.

Here n is the length of seq.

Annotated solutionC++ · one pass · parity of the current nesting level

CPPAssign each parenthesis to the parity group of the pair's current nesting level.

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        int n = seq.size();
        vector<int> ans(n);
        int depth = 0;

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

        return ans;
    }
};