Maximum Nesting Depth of Two Valid Parentheses Strings
A string is a valid parentheses string, denoted VPS, if and only if it consists only of "(" and ")" characters and satisfies one of the following rules:
- It is the empty string.
- It can be written as
AB, whereAandBare VPS's. - It can be written as
(A), whereAis a VPS.
The nesting depth depth(S) of a VPS S is defined as follows:
depth("") = 0.depth(A + B) = max(depth(A), depth(B)), whereAandBare VPS's.depth("(" + A + ")") = 1 + depth(A), whereAis a VPS.
Given a VPS seq, split it into two disjoint subsequences A and B such that:
AandBare both VPS's.A.length + B.length = seq.length.- The subsequences do not necessarily have to be contiguous.
Choose any valid split such that max(depth(A), depth(B)) is minimized.
Return an answer array of length seq.length encoding the split: answer[i] = 0 if seq[i] is part of A, otherwise answer[i] = 1. Multiple valid answers may exist, and you may return any of them.
Example 1
Input
seq = "(()())"Output
[0,1,1,1,1,0]This assignment splits the parentheses into two valid subsequences while minimizing the maximum nesting depth between them.
Example 2
Input
seq = "()(())()"Output
[0,0,0,1,1,0,1,1]This assignment produces two valid parentheses subsequences with the minimum possible maximum nesting depth.
Constraints
- 1 <= seq.size <= 10000