## Algorithm

Problem Name: 1111. Maximum Nesting Depth of Two Valid Parentheses Strings

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 with `B`), where `A` and `B` are VPS's, or
• It can be written as `(A)`, where `A` 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))`, where `A` and `B` are VPS's
• `depth("(" + A + ")") = 1 + depth(A)`, where `A` 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`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````start coding.
class Solution {
public int[] maxDepthAfterSplit(String seq) {
int[] result = new int[seq.length()];
int idx = 0;
int depth = 0;
for (char c : seq.toCharArray()) {
result[idx++] = c == '(' ? (depth++ % 2) : (--depth % 2);
}
return result;
}
}
..``````
Copy The Code &

Input

cmd
seq = "(()())"

Output

cmd
[0,1,1,1,1,0]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const maxDepthAfterSplit = function(seq) {
const n = seq.length
const res = Array(n).fill(0)
let depth = 0
for(let i = 0; i < n; i++) {
const ch = seq[i]
if(ch === '(') {
depth++
}
res[i] = depth % 2
if(ch === ')') depth--
}
return res
};
``````
Copy The Code &

Input

cmd
seq = "(()())"

Output

cmd
[0,1,1,1,1,0]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def maxDepthAfterSplit(self, seq: str) -> List[int]:
stack = []
res =  * len(seq)
for i, c in enumerate(seq):
if c == '(':
stack.append(i if not stack or stack[-1] < 0 else -i)
else:
ind = stack.pop()
if ind >= 0:
res[i] = res[ind] = 1
return res
``````
Copy The Code &

Input

cmd
seq = "()(())()"

Output

cmd
[0,0,0,1,1,0,1,1]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _1111_MaximumNestingDepthOfTwoValidParenthesesStrings
{
public int[] MaxDepthAfterSplit(string seq)
{
var result = new int[seq.Length];
var currDepth = -1;

for (var i = 0; i < seq.Length; i++)
{
if (seq[i] == '(')
{
currDepth++;
result[i] = currDepth % 2;
}
else
{
result[i] = currDepth % 2;
currDepth--;
}
}

return result;
}
}
}
``````
Copy The Code &

Input

cmd
seq = "()(())()"

Output

cmd
[0,0,0,1,1,0,1,1]