1111. Maximum Nesting Depth of Two Valid Parentheses Strings
Description
A string is a valid parentheses string (denoted VPS) if and only if it consists of "("
and ")"
characters only, and:
- It is the empty string, or
- It can be written as
AB
(A
concatenated withB
), whereA
andB
are VPS's, or - It can be written as
(A)
, whereA
is a VPS.
We can similarly define the nesting depth depth(S)
of any VPS S
as follows:
depth("") = 0
depth(A + B) = max(depth(A), depth(B))
, whereA
andB
are VPS'sdepth("(" + A + ")") = 1 + depth(A)
, whereA
is a VPS.
For example, ""
, "()()"
, and "()(()())"
are VPS's (with nesting depths 0, 1, and 2), and ")("
and "(()"
are not VPS's.
Given a VPS seq, split it into two disjoint subsequences A
and B
, such that A
and B
are VPS's (and A.length + B.length = seq.length
).
Now choose any such A
and B
such that max(depth(A), depth(B))
is the minimum possible value.
Return an answer
array (of length seq.length
) that encodes such a choice of A
and B
: answer[i] = 0
if seq[i]
is part of A
, else answer[i] = 1
. Note that even though multiple answers may exist, you may return any of them.
Example 1:
Input: seq = "(()())" Output: [0,1,1,1,1,0]
Example 2:
Input: seq = "()(())()" Output: [0,0,0,1,1,0,1,1]
Constraints:
1 <= seq.size <= 10000
Solutions
Solution 1: Greedy
We use a variable $x$ to maintain the current balance of parentheses, which is the number of left parentheses minus the number of right parentheses.
We traverse the string $seq$, updating the value of $x$. If $x$ is odd, we assign the current left parenthesis to $A$, otherwise we assign it to $B$.
The time complexity is $O(n)$, where $n$ is the length of the string $seq$. Ignoring the space consumption of the answer, the space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|