A valid parentheses string is defined by the following rules:

• It is the empty string "".

• It can be written as the concatenation of two valid parentheses strings A and B.

• It can be written as ( followed by a valid parentheses string A followed by ).

The nesting depth of a valid parentheses string is defined as follows:

• The depth of "" is $0$.

• The depth of A concatenated with B is $\max( ext{depth}(A), ext{depth}(B))$, where A and B are valid parentheses strings.

• The depth of ( followed by A followed by ) is $1 + ext{depth}(A)$, where A is a valid parentheses string.

Given a valid parentheses string seq, split its characters into two disjoint subsequences A and B such that both A and B are valid parentheses strings, and $\max( ext{depth}(A), ext{depth}(B))$ is minimized.

Return an array answer of length seq.size where answer[i] = 0 if seq[i] is assigned to A, and answer[i] = 1 if seq[i] is assigned to B. If there are multiple valid solutions, any of them may be returned.

Constraints:

• $1 \leq$ seq.size $\leq 10000$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.