Move from brute-force thinking to an efficient approach using stack strategy.
A string is a valid parentheses string (denoted VPS) if and only if it consists of "(" and ")" characters only, and:
AB (A concatenated with B), where A and B are VPS's, or(A), where A is a VPS.We can similarly define the nesting depth depth(S) of any VPS S as follows:
depth("") = 0depth(A + B) = max(depth(A), depth(B)), where A and B are VPS'sdepth("(" + 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 <= 10000Problem summary: 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
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Stack
"(()())"
"()(())()"
maximum-nesting-depth-of-the-parentheses)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1111: Maximum Nesting Depth of Two Valid Parentheses Strings
class Solution {
public int[] maxDepthAfterSplit(String seq) {
int n = seq.length();
int[] ans = new int[n];
for (int i = 0, x = 0; i < n; ++i) {
if (seq.charAt(i) == '(') {
ans[i] = x++ & 1;
} else {
ans[i] = --x & 1;
}
}
return ans;
}
}
// Accepted solution for LeetCode #1111: Maximum Nesting Depth of Two Valid Parentheses Strings
func maxDepthAfterSplit(seq string) []int {
n := len(seq)
ans := make([]int, n)
for i, x := 0, 0; i < n; i++ {
if seq[i] == '(' {
ans[i] = x & 1
x++
} else {
x--
ans[i] = x & 1
}
}
return ans
}
# Accepted solution for LeetCode #1111: Maximum Nesting Depth of Two Valid Parentheses Strings
class Solution:
def maxDepthAfterSplit(self, seq: str) -> List[int]:
ans = [0] * len(seq)
x = 0
for i, c in enumerate(seq):
if c == "(":
ans[i] = x & 1
x += 1
else:
x -= 1
ans[i] = x & 1
return ans
// Accepted solution for LeetCode #1111: Maximum Nesting Depth of Two Valid Parentheses Strings
struct Solution;
impl Solution {
fn max_depth_after_split(seq: String) -> Vec<i32> {
let n = seq.len();
let mut level = 0;
let mut res: Vec<i32> = vec![0; n];
for (i, c) in seq.char_indices() {
if c == '(' {
res[i] = level % 2;
level += 1;
} else {
level -= 1;
res[i] = level % 2;
}
}
res
}
}
#[test]
fn test() {
let seq = "(()())".to_string();
let res = vec![0, 1, 1, 1, 1, 0];
assert_eq!(Solution::max_depth_after_split(seq), res);
let seq = "()(())()".to_string();
let res = vec![0, 0, 0, 1, 1, 0, 0, 0];
assert_eq!(Solution::max_depth_after_split(seq), res);
}
// Accepted solution for LeetCode #1111: Maximum Nesting Depth of Two Valid Parentheses Strings
function maxDepthAfterSplit(seq: string): number[] {
const n = seq.length;
const ans: number[] = new Array(n);
for (let i = 0, x = 0; i < n; ++i) {
if (seq[i] === '(') {
ans[i] = x++ & 1;
} else {
ans[i] = --x & 1;
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.
Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.