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.

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.

Description Solution Video 6:18

1111. Maximum Nesting Depth of Two Valid Parentheses Strings

Q: 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.

Q: 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.

Medium82.9% acceptance3 companies

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

Asked at 3 companies

Bloomreach Microsoft

Google

Topics

Stack String

6:18

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

1111. Maximum Nesting Depth of Two Valid Parentheses Strings

Asked at 3 companies

Topics

Similar problems