Maximum Nesting Depth of Two Valid Parentheses Strings

medium parentheses greedy stack

Problem

A valid parentheses string (VPS) is balanced and well-formed. Given a VPS seq, split it into two disjoint subsequences A and B, both valid, so that max(depth(A), depth(B)) is as small as possible. Return an array answer of the same length where answer[i] is 0 if character seq[i] goes to A and 1 if it goes to B.

Inputseq = "(()())"

Output[0, 1, 1, 1, 1, 0]

The full string nests to depth 2. Splitting by depth parity gives each subsequence depth 1, so the larger depth is minimized.

seq (only '(' and ')')

def max_depth_after_split(seq):
    ans = [0] * len(seq)
    depth = 0
    for i, c in enumerate(seq):
        if c == '(':
            ans[i] = depth % 2
            depth += 1
        else:
            depth -= 1
            ans[i] = depth % 2
    return ans

function maxDepthAfterSplit(seq) {
  const ans = new Array(seq.length);
  let depth = 0;
  for (let i = 0; i < seq.length; i++) {
    if (seq[i] === '(') {
      ans[i] = depth % 2;
      depth++;
    } else {
      depth--;
      ans[i] = depth % 2;
    }
  }
  return ans;
}

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

vector<int> maxDepthAfterSplit(string seq) {
    vector<int> ans(seq.size());
    int depth = 0;
    for (int i = 0; i < (int)seq.size(); i++) {
        if (seq[i] == '(') {
            ans[i] = depth % 2;
            depth++;
        } else {
            depth--;
            ans[i] = depth % 2;
        }
    }
    return ans;
}

Explanation

To make the larger of the two depths as small as possible, you want to spread the nesting across both groups evenly. The neat trick is to assign each character by the parity (odd/even) of its depth: even-depth parens go to group 0, odd-depth parens go to group 1.

We track a running depth as we scan. For an open paren ( we assign it depth % 2 first, then increase the depth. For a close paren ) we decrease the depth first, then assign depth % 2 — this guarantees a close paren gets the same label as its matching open paren.

By alternating groups every level, each group only ever sees about half the nesting, so a string of depth d splits into two valid strings each of depth roughly d/2, which is the smallest possible maximum.

Example: seq = "(()())" nests to depth 2. Labeling by depth parity gives [0,1,1,1,1,0], where the outermost parens (depth 0) are group 0 and the inner ones (depth 1) are group 1. Each subsequence then has depth 1.

It works because matching parens always share the same depth value, so each group stays balanced and valid, while the parity split keeps both groups shallow.

Time: O(n) Space: O(n)