Maximum Nesting Depth of Two Valid Parentheses Strings solution and explanation
Google
9 more videos on this problem
1111. Maximum Nesting Depth of Two Valid Parentheses Strings (LeetCode Weekly Contest 144)Kelvin Chandra · 6:18 · 5K views
LeetCode 1111. Maximum Nesting Depth of Two Valid Parentheses Strings Solution Explained - JavaAlgorithms and Data Structures Course · 12:06 · 1K views
LeetCode 1111 | Maximum Nesting Depth of Two Valid Parentheses Strings | Counter | JavaSleepy Cracker · 3:23 · 814 views
Maximum Nesting Depth of Two Valid Parentheses Strings - LeetCodeCoderPro · 21:57 · 629 views
米开：LeetCode 1111. Maximum Nesting Depth of Two Valid Parentheses StringsM.C米开朗基罗 · 6:06 · 474 views
1111. Maximum Nesting Depth of Two Valid Parentheses Strings (Leetcode Medium)Programming Live with Larry · 8:37 · 414 views
1111. Maximum Nesting Depth of Two Valid Parentheses Strings 有效括号的嵌套深度【LeetCode 力扣题解】LeetCode 力扣 · 15:44 · 414 views
LeetCode 1111: Maximum Nesting Depth of Two Valid Parentheses StringsAlitaCode · 25:51 · 36 views
No Sound Leetcode 1111: Maximum Nesting Depth of Two Valid Parentheses StringsExtremeProgrammer · 1:04 · 6 views
LeetCode Problem #1111 Maximum Nesting Depth of Two valid Parentheses String神戸万事屋 · 0:57 · 1 view
The problem
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(Aconcatenated withB), whereAandBare VPS's, or - It can be written as
(A), whereAis 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)), whereAandBare VPS'sdepth("(" + A + ")") = 1 + depth(A), whereAis 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
Approach overview
Problem Overview: You receive a valid parentheses string s. The task is to split it into two valid parentheses strings A and B such that the maximum nesting depth across both strings is minimized. Instead of constructing the strings directly, you return an array where each index indicates whether that parenthesis belongs to sequence 0 or 1.
The key observation: nesting depth increases when you see ( and decreases when you see ). If you distribute parentheses between two groups while tracking depth, you can ensure neither group accumulates excessive nesting.
Approach 1: Alternating Depth Approach (O(n) time, O(1) space)
This method tracks the current nesting depth while iterating through the string once. Each time you encounter (, increment the depth and assign the parenthesis to group depth % 2. When you see ), assign it using the current depth parity before decrementing. This effectively alternates nested layers between the two groups.
The insight: alternating by depth splits the nesting tree into two balanced halves. Deep levels automatically go to different groups, preventing one sequence from accumulating all the nesting. The algorithm performs a single pass through the string and only maintains an integer depth counter.
This approach is extremely concise and avoids auxiliary structures like stacks. If you already understand how nesting depth evolves in a valid parentheses string, this solution becomes almost mechanical.
Approach 2: Balanced Depth Assignment (O(n) time, O(1) space)
This approach also scans the string once but focuses on balancing how opening and closing parentheses are distributed between the two groups. Maintain a depth counter and decide the assignment based on whether the current level is even or odd. Opening parentheses increase the depth, and closing parentheses decrease it, while assignments ensure both sequences stay balanced.
The idea is similar to splitting a recursion tree into two interleaving layers. Each depth level alternates ownership between the two sequences, guaranteeing that the deepest nesting in the original string gets divided. This keeps the maximum depth of each resulting string close to originalDepth / 2.
Because the input is guaranteed to be valid, no explicit stack is required. A simple counter replaces the usual stack-based parsing commonly used for string parentheses problems.
Recommended for interviews: The alternating depth approach is the expected solution. It runs in O(n) time with O(1) extra space and demonstrates that you understand how nesting depth evolves in a parentheses string. Showing awareness of the depth distribution idea proves you can optimize beyond naive stack simulations.
Approach 1: Alternating Depth Approach
An intuitive approach to minimize the maximum nesting depth of two valid parentheses sequences (A and B) is by alternating assignment of parenthesis indexes between the two sequences. The idea is to alternate between 0 and 1 whenever you encounter an opening parenthesis '('. Thus, you distribute the potential depth evenly, and consequently, the resulting nesting depth is minimized.
For a closing parenthesis ')', match it with the corresponding '(' in the same group it was started, which is straightforward given our alternating method.
def maxDepthAfterSplit(seq):
answer = []
depth = 0
for char in seq:
if char == '(': # open bracket
answer.append(depth % 2)
depth += 1
else: # close bracket
depth -= 1
answer.append(depth % 2)
return answer
seq = "()(())()"
print(maxDepthAfterSplit(seq))import java.util.Arrays;
public class MaxDepthSplit {
public static int[] maxDepthAfterSplit(String seq) {
int n = seq.length();
int[] answer = new int[n];
int depth = 0;
for (int i = 0; i < n; ++i) {
if (seq.charAt(i) == '(') {
answer[i] = depth % 2;
depth++;
} else {
depth--;
answer[i] = depth % 2;
}
}
return answer;
}
public static void main(String[] args) {
String seq = "()(())()";
System.out.println(Arrays.toString(maxDepthAfterSplit(seq)));
}
}#include <vector>
#include <string>
#include <iostream>
std::vector<int> maxDepthAfterSplit(const std::string& seq) {
std::vector<int> answer(seq.size(), 0);
int depth = 0;
for (size_t i = 0; i < seq.size(); ++i) {
if (seq[i] == '(') {
answer[i] = depth % 2;
++depth;
} else {
--depth;
answer[i] = depth % 2;
}
}
return answer;
}
int main() {
std::string seq = "()(())()";
auto result = maxDepthAfterSplit(seq);
for (int val : result) {
std::cout << val << " ";
}
return 0;
}function maxDepthAfterSplit(seq) {
const answer = new Array(seq.length);
let depth = 0;
for (let i = 0; i < seq.length; i++) {
if (seq[i] === '(') {
answer[i] = depth % 2;
depth++;
} else {
depth--;
answer[i] = depth % 2;
}
}
return answer;
}
const seq = "()(())()";
console.log(maxDepthAfterSplit(seq));#include <stdio.h>
#include <string.h>
#define MAX 10000
void maxDepthAfterSplit(const char* seq, int* answer) {
int n = strlen(seq);
int depth = 0;
for (int i = 0; i < n; i++) {
if (seq[i] == '(') {
answer[i] = depth % 2;
depth++;
} else {
depth--;
answer[i] = depth % 2;
}
}
}
int main() {
const char* seq = "(()())";
int answer[MAX];
maxDepthAfterSplit(seq, answer);
for (int i = 0; i < strlen(seq); i++) {
printf("%d ", answer[i]);
}
return 0;
}using System;
public class MaxDepthSplit {
public static int[] MaxDepthAfterSplit(string seq) {
int n = seq.Length;
int[] answer = new int[n];
int depth = 0;
for (int i = 0; i < n; i++) {
if (seq[i] == '(') {
answer[i] = depth % 2;
depth++;
} else {
depth--;
answer[i] = depth % 2;
}
}
return answer;
}
public static void Main() {
string seq = "()(())()";
int[] result = MaxDepthAfterSplit(seq);
Console.WriteLine(string.Join(", ", result));
}
}In Python, the task of alternating assignments is similarly achieved by appending the current depth's parity to the answer list.
Time Complexity: O(n) - We process each character in the string.
Space Complexity: O(n) - We maintain a list of the same length as the input string.
Approach 2: Balanced Depth Assignment
Another approach involves maintaining two counters to represent the potential depths of both sequences A and B. At every step, choose the sequence with a smaller current depth for the new '(' encountered and alternate in case of a tie. This ensures that the depths remain as balanced as possible, minimizing the maximum needed depth.
def maxDepthAfterSplit(seq):
answer = []
depthA = depthB = 0
for char in seq:
if char == '(': # open bracket
if depthA < depthB:
answer.append(0)
depthA += 1
else:
answer.append(1)
depthB += 1
else: # close bracket
if depthA > depthB:
answer.append(0)
depthA -= 1
else:
answer.append(1)
depthB -= 1
return answer
seq = "()(())()"
print(maxDepthAfterSplit(seq))import java.util.Arrays;
public class MaxDepthSplit {
public static int[] maxDepthAfterSplit(String seq) {
int n = seq.length();
int[] answer = new int[n];
int depthA = 0, depthB = 0;
for (int i = 0; i < n; ++i) {
if (seq.charAt(i) == '(') {
if (depthA < depthB) {
answer[i] = 0;
depthA++;
} else {
answer[i] = 1;
depthB++;
}
} else {
if (depthA > depthB) {
answer[i] = 0;
depthA--;
} else {
answer[i] = 1;
depthB--;
}
}
}
return answer;
}
public static void main(String[] args) {
String seq = "()(())()";
System.out.println(Arrays.toString(maxDepthAfterSplit(seq)));
}
}#include <vector>
#include <string>
#include <iostream>
std::vector<int> maxDepthAfterSplit(const std::string& seq) {
std::vector<int> answer(seq.size(), 0);
int depthA = 0, depthB = 0;
for (size_t i = 0; i < seq.size(); ++i) {
if (seq[i] == '(') {
if (depthA < depthB) {
answer[i] = 0;
depthA++;
} else {
answer[i] = 1;
depthB++;
}
} else {
if (depthA > depthB) {
answer[i] = 0;
depthA--;
} else {
answer[i] = 1;
depthB--;
}
}
}
return answer;
}
int main() {
std::string seq = "()(())()";
auto result = maxDepthAfterSplit(seq);
for (int val : result) {
std::cout << val << " ";
}
return 0;
}function maxDepthAfterSplit(seq) {
const answer = new Array(seq.length);
let depthA = 0, depthB = 0;
for (let i = 0; i < seq.length; i++) {
if (seq[i] === '(') {
if (depthA < depthB) {
answer[i] = 0;
depthA++;
} else {
answer[i] = 1;
depthB++;
}
} else {
if (depthA > depthB) {
answer[i] = 0;
depthA--;
} else {
answer[i] = 1;
depthB--;
}
}
}
return answer;
}
const seq = "()(())()";
console.log(maxDepthAfterSplit(seq));#include <stdio.h>
#include <string.h>
#define MAX 10000
void maxDepthAfterSplit(const char* seq, int* answer) {
int n = strlen(seq);
int depthA = 0, depthB = 0;
for (int i = 0; i < n; ++i) {
if (seq[i] == '(') {
if (depthA < depthB) {
answer[i] = 0;
depthA++;
} else {
answer[i] = 1;
depthB++;
}
} else {
if (depthA > depthB) {
answer[i] = 0;
depthA--;
} else {
answer[i] = 1;
depthB--;
}
}
}
}
int main() {
const char* seq = "(()())";
int answer[MAX];
maxDepthAfterSplit(seq, answer);
for (int i = 0; i < strlen(seq); i++) {
printf("%d ", answer[i]);
}
return 0;
}using System;
public class MaxDepthSplit {
public static int[] MaxDepthAfterSplit(string seq) {
int n = seq.Length;
int[] answer = new int[n];
int depthA = 0, depthB = 0;
for (int i = 0; i < n; i++) {
if (seq[i] == '(') {
if (depthA < depthB) {
answer[i] = 0;
depthA++;
} else {
answer[i] = 1;
depthB++;
}
} else {
if (depthA > depthB) {
answer[i] = 0;
depthA--;
} else {
answer[i] = 1;
depthB--;
}
}
}
return answer;
}
public static void Main() {
string seq = "()(())()";
int[] result = MaxDepthAfterSplit(seq);
Console.WriteLine(string.Join(", ", result));
}
}In this Python solution, we utilize two depth variables noting the potential increase of sequence A or B depth whenever we read an opening bracket. This balances both sub-sequence depths.
Time Complexity: O(n) - Each character is processed linearly.
Space Complexity: O(n) - Usage of answer list corresponding to string's length.
Approach 3: 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).
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;
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Alternating Depth Approach | Time Complexity: O(n) - We process each character in the string. |
| Balanced Depth Assignment | Time Complexity: O(n) - Each character is processed linearly. |
| Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Alternating Depth Approach | O(n) | O(1) | Best general solution. Minimal code and evenly splits nesting depth. |
| Balanced Depth Assignment | O(n) | O(1) | Useful when reasoning about distributing depth levels explicitly. |
Frequently asked questions
Is Maximum Nesting Depth of Two Valid Parentheses Strings easy or hard?
The problem is rated Medium on LeetCode. The implementation is simple once you understand how nesting depth works, but recognizing that depth parity can split the parentheses efficiently requires insight into how valid parentheses strings behave.
Maximum Nesting Depth of Two Valid Parentheses Strings Python/Java solution
In Python or Java, iterate through the string and maintain a depth variable. Assign each parenthesis to either group 0 or 1 based on whether the current depth is even or odd. Both implementations run in O(n) time and use O(1) extra space besides the output array.
How to solve Maximum Nesting Depth of Two Valid Parentheses Strings in O(n)?
Iterate through the string while maintaining a nesting depth counter. For each '(' increment depth and assign the parenthesis to group depth % 2. For each ')' assign it using the current depth parity before decrementing. This single-pass strategy distributes nesting layers across two valid sequences efficiently.
What is the best approach for Maximum Nesting Depth of Two Valid Parentheses Strings?
The alternating depth approach is the most efficient and widely used solution. It tracks the current nesting depth while iterating through the string and assigns each parenthesis based on depth parity. This splits nested layers evenly between two sequences. The algorithm runs in O(n) time with O(1) extra space.
Is Maximum Nesting Depth of Two Valid Parentheses Strings asked at Google/Amazon/Meta?
This problem belongs to a common category of parentheses and depth-tracking questions frequently seen in interviews at companies like Google, Amazon, and Meta. Variations involving nesting depth, balanced parentheses validation, and stack simulations appear regularly in coding interviews.
What data structure is used in Maximum Nesting Depth of Two Valid Parentheses Strings?
A stack is the classic structure for parsing parentheses problems, but this problem can be solved using just an integer depth counter. Because the input string is guaranteed to be valid, tracking depth changes is enough to simulate stack behavior without storing characters.
What is the time complexity of Maximum Nesting Depth of Two Valid Parentheses Strings?
The optimal solutions run in O(n) time where n is the length of the parentheses string. The algorithm performs a single pass through the characters and updates a depth counter. Space complexity is O(1) since only a few integer variables are maintained.