LeetCode 1111. Maximum Nesting Depth of Two Valid Parentheses Strings Solution in Java, C++, Python & More | Explanation + Code

Description

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). The subsequences may not necessarily be contiguous.

For example, for the sequence 123456789, one possible split is:

• A = {1, 3, 5, 7, 9},

• B = {2, 4, 6, 8}.

This corresponds to the output [0, 1, 0, 1, 0, 1, 0, 1, 0]  where 0 indicates membership in A and 1 indicates membership in B.

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

Solutions

Solution 1: 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).

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

class Solution { public: vector<int> maxDepthAfterSplit(string seq) { int n = seq.size(); vector<int> ans(n); for (int i = 0, x = 0; i < n; ++i) { if (seq[i] == '(') { ans[i] = x++ & 1; } else { ans[i] = --x & 1; } } return ans; } };(code-box)

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 }(code-box)

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; }(code-box)