Maximum Nesting Depth of the Parentheses

Easy
226.

Maximum Nesting Depth of the Parentheses

Maximum Nesting Depth of the Parentheses is an easy coding problem on strings and stack, asked in Amazon and Adobe interviews.

Given a valid parentheses string s — a string of digits, +, -, *, / and balanced parentheses — return the maximum nesting depth of its parentheses.

The nesting depth of a string with no parentheses is 0.

Example 1

Input
s = "(1+(2*3)+((8)/4))+1"
Output
3
Explanation
The 8 sits three levels deep.

Example 2

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

Example 3

Input
s = "1+2"
Output
0

Constraints

  • 1 <= s.length <= 40
  • s is a valid parentheses string.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var maxDepth = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Nesting Depth of the Parentheses — Solution

Maximum Nesting Depth of the Parentheses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Maximum Nesting Depth of the Parentheses is an easy coding problem on strings and stack, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Strings, Stack
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a valid parentheses string s — a string of digits, +, -, *, / and balanced parentheses — return the maximum nesting depth of its parentheses.

The nesting depth of a string with no parentheses is 0.

Example 1

Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation: The 8 sits three levels deep.

Example 2

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

Example 3

Input: s = "1+2"
Output: 0

Constraints

  • 1 <= s.length <= 40
  • s is a valid parentheses string.

Hints for Maximum Nesting Depth of the Parentheses

  1. Hint 1

    No stack is needed — only the stack's height matters.

  2. Hint 2

    Increment a counter on (, decrement on ), and record the largest value the counter ever reaches.

How to solve Maximum Nesting Depth of the Parentheses

Only the stack's height matters: count up on (, down on ), and remember the peak.

Approach

  1. Set depth = best = 0.
  2. For (, increment depth and update best; for ), decrement.
  3. Return best.

Why it works

In a valid parentheses string the running counter equals the number of currently open brackets, and the maximum value it takes is the deepest nesting.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Digits and operators are ignored entirely.
  • A string with no parentheses returns 0 naturally.

Reference solution

Python

def maxDepth(s: str) -> int:
    depth = best = 0
    for ch in s:
        if ch == "(":
            depth += 1
            if depth > best:
                best = depth
        elif ch == ")":
            depth -= 1
    return best

Java

public static int maxDepth(String s) {
    int depth = 0, best = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            depth++;
            if (depth > best) best = depth;
        } else if (c == ')') {
            depth--;
        }
    }
    return best;
}

C++

int maxDepth(string s) {
    int depth = 0, best = 0;
    for (char c : s) {
        if (c == '(') {
            depth++;
            if (depth > best) best = depth;
        } else if (c == ')') {
            depth--;
        }
    }
    return best;
}

JavaScript

var maxDepth = function(s) {
    let depth = 0, best = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === "(") {
            depth++;
            if (depth > best) best = depth;
        } else if (s[i] === ")") {
            depth--;
        }
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Stack Data Structure