Skip to main content

Stack

Maximum Nesting Depth of the Parentheses

Given a valid parentheses string s, return the nesting depth of s. The nesting depth is the maximum number of nested parentheses.

What is a valid Parentheses ?

If for each opening parentheses, there is a closing parentheses, then this pair of parentheses is known as a valid parentheses.
For example:-
"()()" is a valid parentheses.
"(())" is a valid parentheses.
"()((xyz))" is a valid parentheses.

But, ")())" is not a valid parentheses.

Examples

Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation: Digit 8 is inside of 3 nested parentheses in the string.

Input: s = "(1)+((2))+(((3)))"
Output: 3
Explanation: Digit 3 is inside of 3 nested parentheses in the string.

Input: s = "()(())((()()))"
Output: 3

Constraints

  • 1 <= s.length <= 100
  • s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
  • It is guaranteed that parentheses expression s is a VPS.
💡
Try solving it Yourself first !
The problem statement given asks us to find out the maximum depth of parentheses of the string. Let's see how we can come with a solution. Usually this problem statement requires logical thinking rather than just the brute force approach. So, let's figure out the approach and understand it !!

Optimal Approach

Intuition

Before moving to the approach, we need not worry whether for each opening parentheses there is a closing parentheses is there or not. We are already given a valid parentheses which means for every opening parentheses there is a closing parentheses.

Let's first understand what we have to find out. We are given a string s that consists of numbers (like 1, 2, 3, etc.), mathematical operators (+, -, *, /) and parentheses (( and ))

Our job is to figure out the maximum nesting depth of the parentheses. In simpler terms, nesting depth means: how "deep" the parentheses are inside each other at any point.

 What does that mean??
Think of parentheses as containers that can be "inside" one another.
Here are some examples to help visualize this:
1. "()", there’s only one pair of parentheses so the depth = 1.
2. "(())", here the first "(" starts, and inside it, there's another pair so the depth becomes 2.
3. "((()))", similarly one set of parentheses is inside another, which is also inside another and the depth becomes 3.
4. "()()" ,these are separate pairs, not inside each other. Here, depth won't be 2 since they are not inside each other. Hence, Depth = 1.

So, our goal is to find the maximum depth in any part of the string.

What all did we observe from the 2nd example ??
When the string is s="(())".
While iterating from first when we encountered the 0th character as "(", can we say that now depth will surely be one or more than that?? Yes, because for "(" there will surely be one ")" in the later part of string. So, are we saying that we increase the depth by 1.

In other words, if we are storing the maximum nesting depth in "maxDepth" and the current Depth is "depth". What we will do is:

When current character = '(' , we update depth= depth+1 and maxDepth as well !!

Whenever, our depth is increased we need to make sure that the value is compared with the maxDepth and updated accordingly.

Now, when we move forward to the 1st character, again we encounter a "(".
Are we again saying that now the depth is increased because for this "(" there will be a ")" ones too ?? Yes, so we blindly increment the depth by 1.
Now, depth becomes 2.

Next, we encounter a ")" at the 2nd index. What does it mean? Shall we still increase it??
No, now the nesting depth will decrease by 1. Since, we have already two opening parentheses.

So, when current character = ')', we update depth= depth-1

But, our string will contain all alphabets i.e. numerals and operators. Do we need to consider them as well??
No, our solution is only related to parentheses, so our primary focus is on tracking the "(" and ")".

Approach

Step 1: Initialize maxDepth to 0. Initialize currDepth to 0

Step 2: Loop through each character in the string:

  • If the character is '(': Increment currDepth and update maxDepth as the maximum of currDepth and maxDepth
  • Else if the character is ')': Decrement currDepth

Step 3: Return maxDepth.

Dry-Run

Input
s = "(1+(2*3)+((8)/4))+1"
Output: 3

Initial Values: maxDepth = 0, currDepth = 0

Step-by-Step Iteration:
Character: (

  • currDepth++ → currDepth = 1
  • maxDepth = max(1, 0) → maxDepth = 1

Character: 1 ,No change.

Character: + ,No change.

Character: (

  • currDepth++ → currDepth = 2
  • maxDepth = max(2, 1) → maxDepth = 2

Character: 2, No change.

Character: *, No change.

Character: 3, No change.

Character: )

  • currDepth-- → currDepth = 1

Character: +, No change.

Character: (

  • currDepth++ → currDepth = 2
  • maxDepth = max(2, 2) → maxDepth = 2

Character: (

  • currDepth++ → currDepth = 3
  • maxDepth = max(3, 2) → maxDepth = 3

Character: 8, No change.

Character: /, No change.

Character: 4, No change.

Character: )

  • currDepth-- → currDepth = 2

Character: )

  • currDepth-- → currDepth = 1

Character: )

  • currDepth-- → currDepth = 0

Character: +, No change.

Character: 1, No change.

Final Values:

  • maxDepth = 3
  • currDepth = 0

Output: 3

Optimal Code in all Languages.
1. C++ Try on Compiler 
class Solution {
public:
    // Method to find the maximum depth of nested parentheses
    int maxDepth(string s) {

        // Initialize maxDepth to store the maximum depth found
        int maxDepth = 0;

        // Initialize depth to track the current depth
        int depth = 0;

        // Loop through each character in the string
        for (char curr : s) {

            // If the current character is '(', increase depth
            if (curr == '(') {
                depth++;

                // Update maxDepth with the maximum value of depth and maxDepth
                maxDepth = max(depth, maxDepth);
            }

            // If the current character is ')', decrease depth
            else if (curr == ')') {
                depth--;
            }
        }

        // Return the maximum depth found
        return maxDepth;
    }
};

2. Java Try on Compiler 
class Solution {

    // Method to find the maximum depth of nested parentheses
    public int maxDepth(String s) {
        
        // Initialize maxDepth to store the maximum depth found
        int maxDepth = 0;

        // Initialize depth to track the current depth
        int depth = 0;

        // Loop through each character in the string
        for (int i = 0; i < s.length(); i++) {

            // Get the current character
            char curr = s.charAt(i);

            // If the current character is '(', increase depth
            if (curr == '(') {
                depth++;

                // Update maxDepth with the maximum value of depth and maxDepth
                maxDepth = Math.max(depth, maxDepth);
            }

            // If the current character is ')', decrease depth
            else if (curr == ')') {
                depth--;
            }
        }

        // Return the maximum depth found
        return maxDepth;
    }
}

3. Python Try on Compiler 
class Solution:
    # Method to find the maximum depth of nested parentheses
    def maxDepth(self, s: str) -> int:

        # Initialize maxDepth to store the maximum depth found
        max_depth = 0

        # Initialize depth to track the current depth
        depth = 0

        # Loop through each character in the string
        for curr in s:

            # If the current character is '(', increase depth
            if curr == '(':
                depth += 1

                # Update max_depth with the maximum value of depth and max_depth
                max_depth = max(depth, max_depth)

            # If the current character is ')', decrease depth
            elif curr == ')':
                depth -= 1

        # Return the maximum depth found
        return max_depth

4. JavaScript Try on Compiler 
var maxDepth = function(s) {
    // Initialize variables to track the maximum depth and current depth
    let maxDepth = 0;
    let depth = 0;

    // Iterate through each character in the input string
    for (let i = 0; i < s.length; i++) {

        // Get the current character
        const curr = s[i];

        // If the current character is '(', increment the depth and update maxDepth
        if (curr === '(') {
            depth++;
            maxDepth = Math.max(depth, maxDepth);
        } 
        
        // If the current character is ')', decrement the depth
        else if (curr === ')') {
            depth--;
        }
    }

    // Return the maximum depth of nested parentheses
    return maxDepth;
};

Time Complexity: O(n)

We traverse the string once which will take O(n) time.
We have two conditional statements inside the loop which will take constant time.
Usage of Math.max() function will take O(1) runtime.
So, the total time complexity is: O(n)+ O(1) = O(n)

Space Complexity: O(1)

Auxiliary Space Complexity
Auxiliary Space Complexity refers to the extra space requred by an algorithm other than the input space.
We use the variable "maxDepth" and "depth" which accounts from O(1) space.

Total Space Complexity
Input space: We take a string as an input which will be of length n. So, it occupies O(n) runtime.
Auxiliary Space: O(1).

Overall Total Space Complexity : O(n) + O(1) = O(n)

Learning Tip

For learning purposes, can we think of any other approach rather than the one we figured out.

Did, we just saw a relationship that ,the most recently opened "(" must be the first one to close with ")".
Are you getting any intuition that the last "(" one is related to the first ")".

Last one first out !!

It is a Stack !!
Let's think how we can figure the solution using a Stack.
While calculating the maximum nesting depth, we kept two things in our mind.
One is, whenever we ecounetered "(", we will increment the depth and whenever we ecountered ")", we will decrement the depth.
That means for each "(" we see check the ")".
If it’s "(" : Push it onto the stack (we’re going deeper).
If it’s ")": Pop one item from the stack (we’re closing a level).

Parallelly, we will be checking the maximum nesting depth.

Dry-Run

Input: "(1+(2*3)+((8)/4))+1"
Output:3

Start with an empty stack. ans = 0.
Go through each character:

  1. '(': Push to stack. Stack size = 1. ans = max(0, 1) = 1.
  2. '1': Ignore, it’s not a parenthesis.
  3. '+': Ignore.
  4. '(': Push to stack. Stack size = 2. ans = max(1, 2) = 2.
  5. '2': Ignore.
  6. '*': Ignore.
  7. '3': Ignore.
  8. ')': Pop from stack. Stack size = 1.
  9. '+': Ignore.
  10. '(': Push to stack. Stack size = 2.
  11. '(': Push to stack. Stack size = 3. ans = max(2, 3) = 3.
  12. '8': Ignore.
  13. ')': Pop from stack. Stack size = 2.
  14. '/': Ignore.
  15. '4': Ignore.
  16. ')': Pop from stack. Stack size = 1.
  17. ')': Pop from stack. Stack size = 0.
  18. '+': Ignore.
  19. '1': Ignore.

Final ans = 3.

Then, why is it not considered the most efficient ?

Using a stack will build up our problem solving skills but in this question, we were able to solve the question is O(1) space. However, if we use a stack it will result is O(n/2) = O(n) space.

Similar Questions

Now we have successfully tackled this problem, let's try these similar problems.

Remove Outermost Parentheses

A valid parentheses string is either empty "", "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation.

  • For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.

A valid parentheses string s is primitive if it is nonempty, and there does not exist a way to split it into s = A + B, with A and B nonempty valid parentheses strings.

Given a valid parentheses string s, consider its primitive decomposition: s = P1 + P2 + ... + Pk, where Pi are primitive valid parentheses strings.

Return s after removing the outermost parentheses of every primitive string in the primitive decomposition of s.

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.

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8