1111. Maximum Nesting Depth of Two Valid Parentheses Strings LeetCode Solution

In this guide, you will get 1111. Maximum Nesting Depth of Two Valid Parentheses Strings LeetCode Solution with the best time and space complexity. The solution to Maximum Nesting Depth of Two Valid Parentheses Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Maximum Nesting Depth of Two Valid Parentheses Strings solution in C++
  4. Maximum Nesting Depth of Two Valid Parentheses Strings solution in Java
  5. Maximum Nesting Depth of Two Valid Parentheses Strings solution in Python
  6. Additional Resources
1111. Maximum Nesting Depth of Two Valid Parentheses Strings LeetCode Solution image

Problem Statement of Maximum Nesting Depth of Two Valid Parentheses Strings

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.

See also  662. Maximum Width of Binary Tree LeetCode Solution

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

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)

1111. Maximum Nesting Depth of Two Valid Parentheses Strings LeetCode Solution in C++

class Solution {
 public:
  vector<int> maxDepthAfterSplit(string seq) {
    vector<int> ans;
    int depth = 1;

    // Put all odd-depth parentheses in one group and even-depth parentheses in
    // the other group.
    for (const char c : seq)
      if (c == '(')
        ans.push_back(++depth % 2);
      else
        ans.push_back(depth-- % 2);

    return ans;
  }
};
/* code provided by PROGIEZ */

1111. Maximum Nesting Depth of Two Valid Parentheses Strings LeetCode Solution in Java

class Solution {
  public int[] maxDepthAfterSplit(String seq) {
    int[] ans = new int[seq.length()];
    int depth = 1;

    // Put all odd-depth parentheses in one group and even-depth parentheses in
    // the other group.
    for (int i = 0; i < seq.length(); ++i)
      if (seq.charAt(i) == '(')
        ans[i] = ++depth % 2;
      else
        ans[i] = depth-- % 2;

    return ans;
  }
}
// code provided by PROGIEZ

1111. Maximum Nesting Depth of Two Valid Parentheses Strings LeetCode Solution in Python

class Solution:
  def maxDepthAfterSplit(self, seq: str) -> list[int]:
    ans = []
    depth = 1

    # Put all odd-depth parentheses in one group and even-depth parentheses in the other group.
    for c in seq:
      if c == '(':
        depth += 1
        ans.append(depth % 2)
      else:
        ans.append(depth % 2)
        depth -= 1

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: