1111. Maximum Nesting Depth of Two Valid Parentheses Strings

MediumStackString
Leetcode Link

Problem Description

The problem requires us to operate on a string that is said to be a valid parentheses string (VPS). A VPS is defined by the following properties:

  • It consists of "(" and ")" characters only.
  • It can be an empty string.
  • It can be the concatenation of two valid parentheses strings, A and B.
  • It can be a string that encapsulates a valid parentheses string within parentheses, like "(A)".

The concept of nesting depth depth(S) is also introduced, which is calculated as follows:

  • depth("") (the depth of an empty string) is 0.
  • depth(A + B) (the depth of the concatenation of two VPS's) is the maximum of the depths of A and B.
  • depth("(" + A + ")") (the depth when a VPS A is within parentheses) is 1 + depth(A).

The task is to split a given VPS seq into two disjoint subsequences A and B. Both A and B should themselves be VPS's, and the total length of A and B should be equal to the length of seq. Out of all possible A and B, we need to find the pair that minimizes the maximum of their depths.

The output should be an array answer where each element is either 0 or 1. answer[i] should be 0 if the character seq[i] is part of the subsequence A, otherwise it’s part of B. Though there can be multiple correct A and B pairs, any valid solution is acceptable.

Intuition

The intuition behind the solution is related to the observation that in a valid parentheses string, a subsequence A can be formed by taking some of the "left parentheses" ( and the matching "right parentheses" ) to keep A as a VPS, while the rest can form the subsequence B. By doing so, we can potentially balance the depth between A and B.

A straightforward approach to split the pairs between A and B is to alternate assignments of the parentheses as we traverse the given seq. Each time we encounter a "left parentheses" (, we assign it to A if we are at an "even level" and to B if we are at an "odd level". When we encounter a "right parentheses" ), we step back one level and then perform the similar alternating assignment.

This alternating assignment helps ensure that we don't create too deep a nesting in any of the subsequences, hence minimizing the maximum depth between them.

To implement this, we keep a counter x to track the current level of depth during the traversal, and toggle the assignment of parentheses based on the current level's parity (even or odd) indicated by x & 1. An even x represents that we assign to sequence A (answer[i] is 0), and an odd x represents that we assign to sequence B (answer[i] is 1).

Learn more about Stack patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Solution Approach

The solution uses a simple algorithm that iterates through the given VPS string seq and assigns each parenthesis to either subsequence A or B based on the current depth level. Here's how it's implemented:

  • Initialize an array ans with the same length as seq to store the assignment of each parenthesis to subsequence A (represented by 0) or B (represented by 1).
  • Initialize a variable x that will keep track of the current depth level as we walk through the string. This variable will increment when a "left parentheses" ( is encountered and decrement when a "right parentheses" ) is encountered.
  • Iterate over the characters of seq using enumerate to have both index i and character c. For each character:
    • If c is a "left parentheses" (, determine if the current depth level x is even or odd by checking x & 1. If it's even (x & 1 is 0), it means we are at an even depth level, so ans[i] is set to 0, indicating the parenthesis belongs to A. If it's odd (x & 1 is 1), ans[i] is set to 1, meaning it belongs to B. After assigning the parenthesis, increment the depth level x.
    • If c is a "right parentheses" ), first decrement the depth level x because we are closing a parenthesis. Then check x & 1 and assign ans[i] in the same way as if it was a "left parentheses".
  • Once the iteration is complete, return the ans array which now represents the VPS split between A and B in such a way that the maximum depth of both is minimized.

This algorithmic approach ensures that the split of parentheses between A and B keeps their respective depths balanced, thus minimizing the maximum depth of any VPS that could be formed by them. No additional data structures are needed beyond the ans array for the output and a single integer variable for depth tracking.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let's consider the VPS sequence seq = "(()())"

We wish to split this sequence into two disjoint subsequences A and B such that the maximum depth of A and B is minimized.

The algorithm goes as follows:

  1. Initialize ans to be an array of the same length as seq. In this case, ans = [0, 0, 0, 0, 0, 0].
  2. Initialize our depth counter, x, to 0.
  3. Now, we iterate through the seq string character by character.

Here's a step-by-step walkthrough:

  • i = 0, c = '('. Since x is 0 (even), ans[i] is set to 0. x increments to 1. Now, ans = [0, 0, 0, 0, 0, 0].
  • i = 1, c = '('. x is 1 (odd), ans[i] is set to 1. x increments to 2. Now, ans = [0, 1, 0, 0, 0, 0].
  • i = 2, c = ')'. Before assignment, we decrement x to 1. Since x is now 1 (odd), ans[i] is set to 1. Now, ans = [0, 1, 1, 0, 0, 0].
  • i = 3, c = '('. x is 1 (odd), ans[i] is set to 1. x increments to 2. Now, ans = [0, 1, 1, 0, 0, 0].
  • i = 4, c = ')'. We decrement x to 1 before assigning. x is 1 (odd), ans[i] is set to 1. Now, ans = [0, 1, 1, 0, 1, 0].
  • i = 5, c = ')'. We decrement x to 0 before assigning. Since x is now 0 (even), ans[i] is set to 0. Now, ans = [0, 1, 1, 0, 1, 0].

So the final ans representing the split is [0, 1, 1, 0, 1, 0]. Here, A consists of the parentheses at positions 0, 3, and 5 corresponding to the VPS "(()", and B consists of the parentheses at positions 1, 2, and 4 corresponding to the VPS "()()". Both A and B are valid parentheses strings and the overall maximum depth is minimized.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxDepthAfterSplit(self, seq: str) -> List[int]:
5        # Initialize an array to store the assignment of depths to each parenthesis.
6        assigned_depth = [0] * len(seq)
7      
8        # Declare a variable to keep track of the current depth level.
9        depth_level = 0
10      
11        # Iterate over each character in the sequence alongside its index.
12        for index, char in enumerate(seq):
13            if char == "(":
14                # If the parenthesis is an opening one, determine the depth.
15                # We use bitwise AND with 1 to alternate between 0 and 1.
16                assigned_depth[index] = depth_level & 1
17                # Increment depth level since we've encountered an opening parenthesis.
18                depth_level += 1
19            else:
20                # If the parenthesis is a closing one, first decrement the depth level.
21                depth_level -= 1
22                # After decreasing the depth level, determine the depth for the closing parenthesis.
23                assigned_depth[index] = depth_level & 1
24      
25        # Return the final array with the assigned depths.
26        return assigned_depth
27
1class Solution {
2    // This method splits the maximum depth of balanced sub-sequences from the given sequence
3    public int[] maxDepthAfterSplit(String seq) {
4        // Get the length of the sequence
5        int n = seq.length();
6        // Initialize the answer array to hold the group assignment of each character in 'seq'
7        int[] answer = new int[n];
8        // Loop through the characters of 'seq'
9        for (int i = 0, depthLevel = 0; i < n; ++i) {
10            // If the current character is an opening parenthesis '('
11            if (seq.charAt(i) == '(') {
12                // Assign the current group based on the parity of 'depthLevel' and increment 'depthLevel'
13                answer[i] = depthLevel++ & 1;
14            } else {
15                // If it's a closing parenthesis ')', decrement 'depthLevel' first
16                // then assign the current group based on the parity of 'depthLevel'
17                answer[i] = --depthLevel & 1;
18            }
19        }
20        // Return the array containing group assignments for each character
21        return answer;
22    }
23}
24
1#include <vector>
2#include <string>
3
4class Solution {
5public:
6    // Function to assign depths after split based on the sequence of parentheses
7    std::vector<int> maxDepthAfterSplit(std::string seq) {
8        int size = seq.size(); // Get the size of the sequence
9        std::vector<int> answer(size); // Initialize a vector to store the answer with the same size as the input
10        for (int i = 0, depth = 0; i < size; ++i) {
11            if (seq[i] == '(') {
12                // If the character is '(', increment the depth and assign the current depth modulo 2 to the answer.
13                // This is because depth alternates for better balancing the depth after splitting.
14                answer[i] = depth++ & 1;
15            } else {
16                // For ')', decrement the depth first because we are ending a level of depth 
17                // before assigning to answer.
18                answer[i] = --depth & 1;
19            }
20            // "& 1" effectively takes the least significant bit of the depth, 
21            // which is equivalent to depth % 2 (but faster), to alternate between 0 and 1.
22        }
23        return answer; // Return the computed vector of depths.
24    }
25};
26
1function maxDepthAfterSplit(seq: string): number[] {
2    const sequenceLength = seq.length;  // The length of the input string
3    const answer: number[] = new Array(sequenceLength);  // Initialize the answer array with the same length as input
4
5    // Initialize variables for iteration and depth calculation
6    let depth = 0;  // Used to track the depth of nested parentheses
7
8    // Loop through each character in the input string
9    for (let index = 0; index < sequenceLength; ++index) {
10        if (seq[index] === '(') {
11            // If the current character is an opening parenthesis, determine which group it belongs to
12            // Use bitwise AND with 1 to alternate groups (0 and 1) as depth increases
13            answer[index] = depth++ & 1;
14        } else {
15            // If the current character is a closing parenthesis, decrement depth first before determining the group
16            // Again, use bitwise AND with 1 to alternate groups
17            answer[index] = --depth & 1;
18        }
19    }
20
21    return answer;  // Return the populated answer array
22}
23
Not Sure What to Study? Take the 2-min Quiz：

In a binary min heap, the maximum element can be found in:

Time and Space Complexity

The given code snippet takes a string seq, representing a sequence of parentheses, and returns a list of integers that correspond to the depth of each parenthesis in a way such that the sequence is split into two sequences A and B, with both being valid parentheses strings and depth ideally balanced.

Time Complexity

The time complexity of this code is O(n). This is because there is a single loop that iterates through the string seq, which is of length n. Within this loop, all operations (assigning ans[i], incrementing or decrementing x, and bitwise comparison with 1) are constant time operations, O(1). Since these constant time operations are repeated n times, the overall time complexity remains linear.

Space Complexity

The space complexity is also O(n). The additional space used by the algorithm is primarily for the output list ans, which has the same length as the input string seq. There are no other data structures that grow with the size of the input, and variables like x and i use constant space. Therefore, the space complexity is directly proportional to the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

How many ways can you arrange the three letters A, B and C?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫