Maximum Nesting Depth of the Parentheses

EASY

Description

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

Example 1:

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

Output: 3

Explanation:

Digit 8 is inside of 3 nested parentheses in the string.

Example 2:

Input: s = "(1)+((2))+(((3)))"

Output: 3

Explanation:

Digit 3 is inside of 3 nested parentheses in the string.

Example 3:

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.

Approaches

Checkout 2 different approaches to solve Maximum Nesting Depth of the Parentheses. Click on different approaches to view the approach and algorithm in detail.

Stack-Based Approach

This approach uses a stack to explicitly track the nesting of parentheses. The depth at any point is determined by the number of elements currently in the stack. While intuitive, it's less space-efficient than the counter-based method.

Algorithm

Initialize maxDepth = 0.
Initialize an empty stack st.
Iterate through each character c in the string s:
- If c is '(':
  - Push c onto the stack st.
  - Update maxDepth = Math.max(maxDepth, st.size()).
- Else if c is ')':
  - Pop an element from the stack st.
Return maxDepth.

We can determine the nesting depth by iterating through the string and using a stack to keep track of open parentheses.

Initialize a variable maxDepth to 0 and an empty stack.
Traverse each character of the input string s.
If the character is an opening parenthesis '(', push it onto the stack. The current depth is now the size of the stack. We update maxDepth with the maximum value seen so far (max(maxDepth, stack.size())).
If the character is a closing parenthesis ')', it signifies the end of a nested level, so we pop from the stack.
Other characters (digits, operators) are ignored as they do not affect the nesting structure.
After the loop finishes, maxDepth will contain the maximum nesting depth encountered.

import java.util.Stack;

class Solution {
    public int maxDepth(String s) {
        int maxDepth = 0;
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(c);
                maxDepth = Math.max(maxDepth, stack.size());
            } else if (c == ')') {
                stack.pop();
            }
        }
        return maxDepth;
    }
}

Complexity Analysis

Time Complexity: O(N), where N is the length of the string `s`. We iterate through the string once, and stack operations (push, pop, size) take constant time on average.Space Complexity: O(D), where D is the maximum nesting depth. In the worst-case scenario, such as a string like `'((...))'`, the stack size can grow up to N/2. Therefore, the space complexity is O(N).

Pros and Cons

Pros:

The logic is very clear and directly models the concept of nesting.
It's a standard way to handle parenthesis-related problems.

Cons:

Requires extra space for the stack, which is not optimal for this specific problem.

Code Solutions

Checking out 5 solutions in different languages for Maximum Nesting Depth of the Parentheses. Click on different languages to view the code.

public class Solution {
    public int MaxDepth(string s) {
        int ans = 0, d = 0;
        foreach(char c in s) {
            if (c == '(') {
                ans = Math.Max(ans, ++d);
            } else if (c == ')') {
                --d;
            }
        }
        return ans;
    }
}

Video Solution

Watch the video walkthrough for Maximum Nesting Depth of the Parentheses

Data Structures:

StringStack

Companies:

Intel |

Maximum Nesting Depth of the Parentheses

Description

Approaches

Stack-Based Approach

Algorithm

Complexity Analysis

Pros and Cons

Code Solutions

Video Solution

Similar Questions

Data Structures:

Companies:

On this page

Subscribe to Scale Engineer newsletter