Maximum Nesting Depth of Two Valid Parentheses Strings
Medium · Stack & Strings · String · Stack
Problem
A valid parentheses string is either empty, two valid strings written one after the other, or a valid string wrapped in ( and ). Its nesting depth is how deeply its parentheses are nested: 0 for the empty string, the larger of the two depths for two strings side by side, and one more than the inside for a wrapped string. For example, "()(())" has depth 2.
You are given a valid parentheses string seq. Give every character to one of two groups, 0 or 1, so that the characters of each group, read in their original order, form a valid parentheses string on their own. Make the larger of the two groups' depths as small as possible.
Return a list answer with answer[i] the group of seq[i]. When several splits are equally good, any of them is accepted.
Examples
Input: seq = "(()())" Output: [1,0,0,0,0,1]
Group 1 gets the outer pair, group 0 the two inner pairs "()()". Both have depth 1, down from 2.
Input: seq = "((()))" Output: [1,0,1,1,0,1]
Group 1 gets levels 1 and 3, "(())", depth 2; group 0 gets level 2, "()". Depth 3 cannot be split into two groups of depth 1.
Input: seq = "()()" Output: [1,1,1,1]
Depth 1 cannot get smaller, so both pairs go to group 1 and group 0 stays empty.
Constraints
- 1 <= len(seq) <= 10^4
- seq contains only ( and ).
- seq is a valid parentheses string.
Approaches
- Try every split — time O(2^n · n), space O(n)
Follow-up
With k groups instead of two, the best possible depth is ceil(D / k), and the same idea reaches it: give the parenthesis pair at level d to group (d - 1) % k, so each group gets every k-th level.
Related problems
Start free on Cariara · Coding problems · System design studio
