Skip to main content
Talentd

Maximum Nesting Depth of Two Valid Parentheses Strings - Solution & Explanation

MediumStringStack17 min readAsked at: Microsoft, Google, Bloomreach
Practice this problem

Problem Statement

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

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.

This C program calculates the depth for each parenthesis in the string using a counter. When an opening parenthesis is encountered, the current depth is recorded modulo 2, alternating the assignment for each opening. For a closing parenthesis, it decrements the depth and then applies the same mod operation to decide on its group allocation.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - We iterate through the string once.
Space Complexity: O(n) - We store the output in an answer array.

Try this approach in the editor →

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.

The approach involves tracking the current depth assigned to both sequences (A and B) and chooses the sequence with the lesser depth to assign the next opening bracket '('. When assigning the closing bracket ')', it ties it to the sequence it was originally paired with. This keeps depth differences minimized.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) - Single pass over the string.
Space Complexity: O(n) - Output storage for answer array.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Alternating Depth Approach

Time Complexity: O(n) - We iterate through the string once.
Space Complexity: O(n) - We store the output in an answer array.

Balanced Depth Assignment

Time Complexity: O(n) - Single pass over the string.
Space Complexity: O(n) - Output storage for answer array.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Alternating Depth ApproachO(n)O(1)Best general solution. Minimal code and evenly splits nesting depth.
Balanced Depth AssignmentO(n)O(1)Useful when reasoning about distributing depth levels explicitly.

Video Solution

1111. Maximum Nesting Depth of Two Valid Parentheses Strings (LeetCode Weekly Contest 144) • Kelvin Chandra • 5,294 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Maximum Nesting Depth of Two Valid Parentheses Strings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Nesting Depth of the Parentheses