1614. Maximum Nesting Depth of the Parentheses

EasyStackString
Leetcode Link

Problem Description

The problem defines a valid parentheses string (VPS) with specific rules:

  1. It can be an empty string "", or any single character that is not "(" or ")".
  2. A string can be considered a VPS if it is the concatenation of two VPS's, denoted as AB.
  3. A string is also a VPS if it is of the form (A), where A is itself a VPS.

Beyond this, the problem introduces the concept of nesting depth. Nesting depth is the maximum level of nested parentheses within any VPS. It's defined as follows:

  • depth("") = 0, for an empty string.
  • depth(C) = 0, where C is any single character other than parentheses.
  • depth(A + B) is the maximum depth between two VPS's A and B.
  • depth("(" + A + ")") is the depth of A plus one, accounting for the additional level of nesting created by surrounding A with parentheses.

The task is to calculate and return the nesting depth of a given string s, which is guaranteed to be a VPS.

Intuition

The solution to determining the nesting depth of a string involves keeping track of the current level of parenthetical depth while iterating through the string character by character. Whenever an opening parenthesis "(" is encountered, we increase the depth, and when a closing parenthesis ")" is encountered, we decrease the depth.

The intuition behind the solution is as follows:

  • A depth tracker variable d is initialized to zero.
  • An answer variable ans is also initialized to zero to keep track of the maximum depth encountered.
  • As we iterate over each character c of the string s:
    • If c is an opening parenthesis (, we increase the d count to indicate that we are going a level deeper.
    • We update the ans variable with the maximum between the current ans and the updated depth d.
    • If c is a closing parenthesis ), we decrease the d count to indicate that we are coming out of a depth level.
  • The ans will contain the maximum depth achieved throughout the iteration and is returned as the result.

This approach is efficient because it operates in linear time, making a single pass through the string, and requires only a constant amount of extra space.

Learn more about Stack patterns.

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

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

Solution Approach

The Reference Solution Approach makes use of a simple yet effective algorithm to find the nesting depth of a valid parentheses string. This approach does not require complex data structures or patterns but relies on basic variables to track the progress. The implementation steps are as follows:

  1. Initialize two integer variables: ans and d to zero. ans will hold our final result, the maximum depth of nesting, and d will keep track of the current depth while iterating through the string.
  2. Iterate over each character c in the input string s.
    • When c is an opening parenthesis (: a. Increase the depth d by 1 because we've entered a new layer of nesting. b. Update the answer ans with the greater of ans or d. This step ensures that ans always contains the maximum depth observed so far.
    • When c is a closing parenthesis ): a. Decrease the depth d by 1 because we've exited a layer of nesting.

Here's a more detailed breakdown of the algorithm using the provided Python code:

  • def maxDepth(self, s: str) -> int: defines a method maxDepth that takes a string s as an input and returns an integer representing the maximum depth.
  • ans = d = 0 sets up our variables: ans to track the maximum depth and d to track the current depth.
  • for c in s: starts a loop over each character in the string.
  • if c == '(': checks if the current character is an opening parenthesis.
  • d += 1 increments the current depth because an opening parenthesis indicates deeper nesting.
  • ans = max(ans, d) updates the maximum depth found so far.
  • elif c == ')': checks if the current character is a closing parenthesis.
  • d -= 1 decrements the current depth because a closing parenthesis indicates that we are stepping out of a level of nesting.
  • return ans returns the highest depth of nesting that was recorded during the iteration through the string.

By maintaining a count of the current depth level with each parenthesis encountered and recording the maximum depth along the way, the algorithm effectively computes the nesting depth of the valid parentheses string with a time complexity of O(n) and a space complexity of O(1), where n is the length of the string s.

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

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the string s = "(ab((cd)e))". Our goal is to determine the maximum nesting depth of this valid parentheses string.

  1. We start with ans = 0 and d = 0. These will keep track of the maximum depth and the current depth, respectively.
  2. Begin iterating over each character in s.
  3. First character: (:
    • Current depth d is increased: d = 1.
    • Update ans: ans = max(0, 1) = 1.
  4. Next characters: ab, there are no parentheses, so d and ans remain unchanged.
  5. Next character: (:
    • Current depth d is increased: d = 2.
    • Update ans: ans = max(1, 2) = 2.
  6. Next characters: cd, there are no parentheses, so d and ans remain unchanged.
  7. Next character: ):
    • Current depth d is decreased: d = 1.
  8. Next character: e, still no parentheses, so d and ans remain unchanged.
  9. Next character: ):
    • Current depth d is decreased: d = 0.
    • The string ends here, and ans holds the maximum depth encountered, which is 2.

At the end of this process, the maximum depth ans is 2, which is the correct nesting depth of the example string s. Throughout this iterative process, we have updated ans whenever a greater depth was achieved and correctly maintained the current depth by incrementing and decrementing d at the opening and closing parentheses, respectively. The linear scan allowed us to calculate the nesting depth in a single pass, fulfilling the efficient performance as outlined in the solution approach.

Solution Implementation

1class Solution:
2    def maxDepth(self, s: str) -> int:
3        # Initialize variables to store the current depth and maximum depth
4        max_depth = current_depth = 0
5      
6        # Iterate through each character in the string
7        for char in s:
8            if char == '(':  # If the character is an opening bracket
9                current_depth += 1  # Increase the current depth by 1
10                max_depth = max(max_depth, current_depth)  # Update the max depth if needed
11            elif char == ')':  # If the character is a closing bracket
12                current_depth -= 1  # Decrease the current depth by 1
13              
14        # Return the maximum depth encountered
15        return max_depth
16
1class Solution {
2    public int maxDepth(String s) {
3        int maxDepth = 0; // This will store the maximum depth of the parentheses
4        int currentDepth = 0; // This will keep track of the current depth
5
6        // Iterating over each character in the string
7        for (int i = 0; i < s.length(); ++i) {
8            char c = s.charAt(i); // Get the current character from the string
9
10            if (c == '(') {
11                // If the character is an opening parenthesis, we increase the current depth
12                currentDepth++;
13
14                // Update the maximum depth if the current depth is greater than the maxDepth observed so far
15                maxDepth = Math.max(maxDepth, currentDepth);
16            } else if (c == ')') {
17                // If the character is a closing parenthesis, we decrease the current depth
18                currentDepth--;
19            }
20            // We ignore all other characters
21        }
22
23        // Returning the maximum depth of nesting of the parentheses encountered in the string
24        return maxDepth;
25    }
26}
27
1#include <algorithm> // For using the max function
2#include <string>    // For using the string type
3
4class Solution {
5public:
6    // Function to find the maximum depth of parentheses in a given string `s`.
7    int maxDepth(string s) {
8        int maxDepth = 0; // To store the maximum depth encountered
9        int currentDepth = 0; // To track the current depth of open parentheses
10      
11        // Iterate through each character in the string
12        for (char& c : s) {
13            if (c == '(') {
14                // Increment the current depth when an opening parenthesis is encountered
15                currentDepth++;
16                // Update the maximum depth encountered so far
17                maxDepth = std::max(maxDepth, currentDepth);
18            } else if (c == ')') {
19                // Decrement the current depth when a closing parenthesis is encountered
20                currentDepth--;
21            }
22            // No action on other characters
23        }
24        // Return the maximum depth of opened parentheses
25        return maxDepth;
26    }
27};
28
1// Function to find the maximum nesting depth of parentheses in a given string.
2function maxDepth(s: string): number {
3    let maxDepth = 0; // This will keep track of the maximum depth encountered
4    let currentDepth = 0; // This will keep track of the current depth
5  
6    // Iterate over each character in the input string
7    for (const char of s) {
8        // If the character is an opening parenthesis, increase the current depth
9        if (char === '(') {
10            currentDepth++;
11            // Update the maximum depth if the current depth exceeds it
12            maxDepth = Math.max(maxDepth, currentDepth);
13        } else if (char === ')') {
14            // If the character is a closing parenthesis, decrease the current depth
15            currentDepth--;
16        }
17        // We ignore all other characters
18    }
19  
20    return maxDepth; // Return the maximum depth encountered
21}
22
Not Sure What to Study? Take the 2-min Quiz：

Which of the following array represent a max heap?

Time and Space Complexity

Time Complexity

The time complexity of the code is a function of the number of characters in the input string, s. The code consists of a single for loop that goes through each character of s exactly once, performing O(1) operations for each character - increasing or decreasing the depth d and updating the maximum depth ans. Therefore, the time complexity is O(n), where n is the length of the input string s.

Space Complexity

The space complexity of the code is O(1). This is because the code uses a fixed number of integer variables ans and d, regardless of the input size. No additional structures that grow with input size are used, which means the space used by the algorithm does not depend on 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:

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

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 👨‍🏫