Maximum Nesting Depth of the Parentheses

easy string stack counter

Problem

Given a valid parentheses string s, return the maximum nesting depth of any pair of parentheses.

Inputs = "(1+(2*3)+((8)/4))+1"

Output3

Inner '8' is enclosed by three open parens.

def max_depth(s):
    cur = best = 0
    for c in s:
        if c == '(':
            cur += 1
            best = max(best, cur)
        elif c == ')':
            cur -= 1
    return best

function maxDepth(s) {
  let cur = 0, best = 0;
  for (const c of s) {
    if (c === '(') { cur++; if (cur > best) best = cur; }
    else if (c === ')') cur--;
  }
  return best;
}

class Solution {
    public int maxDepth(String s) {
        int cur = 0, best = 0;
        for (char c : s.toCharArray()) {
            if (c == '(') { cur++; best = Math.max(best, cur); }
            else if (c == ')') cur--;
        }
        return best;
    }
}

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

Explanation

You do not actually need a stack here — a single counter is enough. The depth goes up by one every time you see an open paren ( and down by one on a close paren ). The answer is simply the highest value that counter ever reaches.

We keep two variables: cur for the current depth and best for the deepest point seen so far. On every ( we do cur += 1 and update best = max(best, cur). On every ) we do cur -= 1. All other characters are ignored.

This mimics a stack of open parens, but since we only care about how tall the stack gets, counting is all we need — that is why the space cost is O(1).

Example: s = "(1+(2*3)+((8)/4))+1". The depth climbs to 1 at the first (, then 2 at the inner pair, and the ((8)) region drives it to 3 before closing. The peak was 3, so the answer is 3.

Because the string is guaranteed valid, the counter never goes negative and the running peak correctly captures the deepest nesting in one pass.

Time: O(n) Space: O(1)