Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Maximum Nesting Depth of the Parentheses

EASYProblemSolveExternal Links

Description

You are given a valid parentheses string (VPS) s. The string may contain digits (0-9), operators (+, -, *, /), and parentheses ((, )).

A VPS is defined recursively:

  • An empty string "" is a VPS.
  • If A is a VPS, then "(" + A + ")" is a VPS.
  • If A and B are both VPS, then A + B is a VPS.

The nesting depth of a VPS is defined as:

  • depth("") = 0
  • depth(A + B) = max(depth(A), depth(B))
  • depth("(" + A + ")") = 1 + depth(A)

In simpler terms, the nesting depth is the maximum number of nested (concentric) opening parentheses at any point in the string. Your task is to return this maximum nesting depth.

Examples

Example 1

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

Output: 3

Explanation: The digit 8 is wrapped inside three layers of parentheses: the outermost (...), then ((...)), then (((...))). No other part of the expression is nested deeper than 3 levels.

Example 2

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

Output: 3

Explanation: The digit 3 is inside three nested parentheses: (((3))). The digit 2 is only inside two nested parentheses ((2)), and the digit 1 is inside just one. The maximum is 3.

Example 3

Input: s = "()(())((()()))"

Output: 3

Explanation: The deepest nesting occurs inside ((()())) where the inner () pairs sit at depth 3.

Constraints

  • 1 ≤ s.length ≤ 100
  • s consists of digits 0-9 and characters +, -, *, /, (, and )
  • It is guaranteed that s is a valid parentheses string (VPS)

Editorial

Brute Force

Intuition

The most natural way to think about nesting depth is to use a stack. Every time we see an opening parenthesis (, we push it onto the stack. Every time we see a closing parenthesis ), we pop from the stack. The size of the stack at any moment tells us the current nesting depth — because the stack holds all the unmatched opening parentheses that surround our current position.

Think of it like walking into nested rooms in a building. Each ( is a door you walk through (entering a deeper room), and each ) is a door you walk back out of. The maximum number of rooms deep you ever reach is the answer. The stack keeps track of all the doors you've walked through but haven't exited yet.

Step-by-Step Explanation

Let's trace through with s = "(1+(2*3)+((8)/4))+1":

Step 1: Initialize an empty stack and max_depth = 0.

Step 2: s[0] = '(' → Push onto stack. Stack: ['(']. Size = 1. max_depth = max(0, 1) = 1.

Step 3: s[1] = '1' → Not a parenthesis, skip.

Step 4: s[2] = '+' → Not a parenthesis, skip.

Step 5: s[3] = '(' → Push. Stack: ['(', '(']. Size = 2. max_depth = max(1, 2) = 2.

Step 6: s[4..6] = '2*3' → Skip non-parenthesis characters.

Step 7: s[7] = ')' → Pop. Stack: ['(']. Size = 1.

Step 8: s[8] = '+' → Skip.

Step 9: s[9] = '(' → Push. Stack: ['(', '(']. Size = 2. max_depth = max(2, 2) = 2.

Step 10: s[10] = '(' → Push. Stack: ['(', '(', '(']. Size = 3. max_depth = max(2, 3) = 3.

Step 11: s[11] = '8' → Skip.

Step 12: s[12] = ')' → Pop. Stack: ['(', '(']. Size = 2.

Step 13: s[13] = '/' → Skip.

Step 14: s[14] = '4' → Skip.

Step 15: s[15] = ')' → Pop. Stack: ['(']. Size = 1.

Step 16: s[16] = ')' → Pop. Stack: []. Size = 0.

Step 17: s[17] = '+' → Skip.

Step 18: s[18] = '1' → Skip.

Result: max_depth = 3.

Stack-Based Nesting Depth — Push on '(', Pop on ')' — Watch how the stack grows each time we enter a nested parenthesis and shrinks when we exit. The maximum stack size at any point is the answer.

Algorithm

  1. Initialize an empty stack and max_depth = 0
  2. For each character c in the string:
    • If c == '(': push it onto the stack; update max_depth = max(max_depth, stack.size())
    • If c == ')': pop from the stack
    • Otherwise: skip (it's a digit or operator)
  3. Return max_depth

Code

#include <stack>
#include <string>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxDepth(string s) {
        stack<char> stk;
        int maxDepth = 0;
        
        for (char c : s) {
            if (c == '(') {
                stk.push(c);
                maxDepth = max(maxDepth, (int)stk.size());
            } else if (c == ')') {
                stk.pop();
            }
        }
        
        return maxDepth;
    }
};
class Solution:
    def maxDepth(self, s: str) -> int:
        stack = []
        max_depth = 0
        
        for c in s:
            if c == '(':
                stack.append(c)
                max_depth = max(max_depth, len(stack))
            elif c == ')':
                stack.pop()
        
        return max_depth
import java.util.Stack;

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

Complexity Analysis

Time Complexity: O(n)

We scan the string once, performing O(1) work per character (push, pop, or skip). Total: O(n) where n is the length of the string.

Space Complexity: O(n)

In the worst case, a string like "(((())))" would push n/2 elements onto the stack before any pops. The stack therefore uses O(n) space.

Why This Approach Is Not Efficient

The stack-based solution is already O(n) in time, which is optimal since we must read every character. However, the O(n) space for the stack is unnecessary.

Notice what we actually use the stack for: we never inspect which specific characters are stored — we only care about the size of the stack. Every push increments the size, every pop decrements it. This is just a counter!

If we replace the entire stack with a single integer variable that tracks the current depth, we get the exact same result with O(1) space. The stack was overkill — an integer counter is all we need.

Optimal Approach - Counter Variable

Intuition

Since we only ever need the stack's size (never its actual contents), we can replace the entire stack with a single integer depth. Increment depth when we see (, decrement when we see ). Track the maximum value depth ever reaches.

This is like counting floors in an elevator. Going up one floor when you enter a (, going down one floor when you hit a ). The highest floor you ever visit is the maximum nesting depth. You don't need to remember every floor you visited (the stack) — just the current floor number (the counter).

Step-by-Step Explanation

Let's trace through with s = "(1+(2*3)+((8)/4))+1":

Step 1: depth = 0, max_depth = 0.

Step 2: s[0] = '(' → depth = 1. max_depth = max(0, 1) = 1.

Step 3: s[1] = '1' → skip. depth stays 1.

Step 4: s[2] = '+' → skip. depth stays 1.

Step 5: s[3] = '(' → depth = 2. max_depth = max(1, 2) = 2.

Step 6: s[4..6] = '2*3' → skip. depth stays 2.

Step 7: s[7] = ')' → depth = 1. max_depth stays 2.

Step 8: s[8] = '+' → skip.

Step 9: s[9] = '(' → depth = 2. max_depth stays 2.

Step 10: s[10] = '(' → depth = 3. max_depth = max(2, 3) = 3.

Step 11: s[11] = '8' → skip.

Step 12: s[12] = ')' → depth = 2.

Step 13: s[13..14] = '/4' → skip.

Step 14: s[15] = ')' → depth = 1.

Step 15: s[16] = ')' → depth = 0.

Step 16: s[17..18] = '+1' → skip.

Result: max_depth = 3.

Counter-Based Depth Tracking — O(1) Space — Watch the depth counter rise and fall as we scan through the expression. The maximum value it reaches is the nesting depth — no stack needed.

Algorithm

  1. Initialize depth = 0 and max_depth = 0
  2. For each character c in the string:
    • If c == '(': increment depth, then update max_depth = max(max_depth, depth)
    • If c == ')': decrement depth
    • Otherwise: skip (digit or operator)
  3. Return max_depth

Code

class Solution {
public:
    int maxDepth(string s) {
        int depth = 0;
        int maxDepth = 0;
        
        for (char c : s) {
            if (c == '(') {
                depth++;
                maxDepth = max(maxDepth, depth);
            } else if (c == ')') {
                depth--;
            }
        }
        
        return maxDepth;
    }
};
class Solution:
    def maxDepth(self, s: str) -> int:
        depth = 0
        max_depth = 0
        
        for c in s:
            if c == '(':
                depth += 1
                max_depth = max(max_depth, depth)
            elif c == ')':
                depth -= 1
        
        return max_depth
class Solution {
    public int maxDepth(String s) {
        int depth = 0;
        int maxDepth = 0;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                depth++;
                maxDepth = Math.max(maxDepth, depth);
            } else if (c == ')') {
                depth--;
            }
        }
        
        return maxDepth;
    }
}

Complexity Analysis

Time Complexity: O(n)

We scan the string exactly once, performing O(1) work per character (one comparison, one increment or decrement, and one max comparison). Total: O(n).

Space Complexity: O(1)

We use only two integer variables (depth and max_depth) regardless of input size. This is a significant improvement over the O(n) stack space from the brute force approach.

This solution is optimal in both time and space: O(n) time is necessary because we must read every character, and O(1) space is the minimum possible for any in-place traversal.