☕ DSA Java Articles

Topics › Strings › Medium String Problems

Maximum Nesting Depth of the Parentheses

Medium TUF ID 674 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A string is a valid parentheses string (VPS) if it is empty, or it is a single character that is not a bracket, or it has the form (A) where A is a VPS, or it is the concatenation AB of two VPS. The nesting depth is defined along the same lines: the empty string and a lone non-bracket character have depth 0, (A) has depth 1 + depth(A), and AB has depth max(depth(A), depth(B)).

You are given a VPS s built from digits, the operators + - * / and round brackets. Return its nesting depth. In plain words: what is the largest number of brackets that are open at the same time while reading s from left to right?

Constraints: 1 ≤ |s| ≤ 100; s is guaranteed to be a valid parentheses string. The Java file also accepts the empty string.

Example 1

s = "(1+(2*3)+((8)/4))+1"
answer = 3              // the digit 8 sits inside three brackets

Example 2

s = "(1)+((2))+(((3)))"
answer = 3              // the last group opens three brackets in a row

Example 3

s = "1+(2*3)/(2-1)"
answer = 1              // two bracket groups, but they are siblings, never nested

Approach 1: Brute force, recount the open brackets at every ‘(‘

Intuition. Pick any position i that holds an opening bracket. How deeply nested is it? Exactly as many brackets are open at that moment as there are ( in s[0..i] minus the ) in s[0..i]: every ) closes exactly one earlier (, and because the string is valid no ) is ever left without a partner. So the depth of the bracket at i is the balance of the prefix ending at i, and the depth of the whole string is the largest such balance over all opening brackets. The brute force simply recomputes that balance from scratch for every (.

Why only at opening brackets? The depth can only reach a new maximum at the instant a bracket opens; between an opening bracket and the next one the balance can only stay the same or fall. So checking at every ( is enough, and checking elsewhere is redundant.

Algorithm.

  1. Set best = 0.
  2. For every index i where s[i] == '(':
  3. Walk j from 0 to i, adding one for each ( and subtracting one for each ); call the result open.
  4. Set best = max(best, open).
  5. Return best.
static int bruteForce(String s) {
    int n = s.length(), best = 0;
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) != '(') continue;
        int open = 0;                                  // unmatched '(' in s[0..i], including this one
        for (int j = 0; j <= i; j++) {
            char c = s.charAt(j);
            if (c == '(') open++;
            else if (c == ')') open--;
        }
        best = Math.max(best, open);
    }
    return best;
}

Complexity. Time O(n^2): each of up to n opening brackets triggers a scan of up to n characters. Space O(1): two counters.

The repeated rescans are pure waste: the balance at position i differs from the balance at position i - 1 by at most one, so the prefix never needs to be read again.

Approach 2: Better, an explicit stack

Intuition. Brackets match in last-opened, first-closed order, which is exactly what a stack models. Push every (, pop on every ). Right after a push the stack holds one entry for every bracket that currently encloses us, so its size at that instant is the nesting depth of the bracket just pushed. The answer is the tallest the stack ever becomes.

This is the general-purpose tool for bracket problems. When the input may be invalid, or several bracket types have to be matched against each other, the stack is genuinely needed because we must know which bracket is on top. Here, as the next approach shows, we never look at the top at all.

Algorithm.

  1. Create an empty stack and set best = 0.
  2. For each character c of s:
    • If c == '(', push it and set best = max(best, stack.size()).
    • If c == ')', pop one entry.
    • Otherwise ignore the character.
  3. Return best.
static int better(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    int best = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            stack.push(c);
            best = Math.max(best, stack.size());
        } else if (c == ')') {
            stack.pop();
        }
    }
    return best;
}

Complexity. Time O(n): one push or pop per bracket, each O(1) on an ArrayDeque. Space O(n): in a string like ((((...)))) the stack grows to n / 2 entries.

Pushing on a stack and never reading what was pushed is a sign that the stack is carrying more information than we use.

Approach 3: Optimal, replace the stack with a counter

Intuition. The stack in Approach 2 only ever contains the character (. We never inspect its top, we only ask for its size. A stack whose contents are irrelevant is just an integer: increment on (, decrement on ). The running value is the current depth and the maximum over the scan is the answer. The validity guarantee means the counter never drops below zero and ends at zero.

Algorithm.

  1. Set depth = 0 and best = 0.
  2. For each character c of s:
    • If c == '(', do depth++ and, if depth > best, set best = depth.
    • If c == ')', do depth--.
  3. Return best.
static int optimal(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;
}

Dry run on s = "(1+(2*3)+((8)/4))+1", showing only the bracket positions:

i s[i] depth after best
0 ( 1 1
3 ( 2 2
7 ) 1 2
9 ( 2 2
10 ( 3 3
12 ) 2 3
15 ) 1 3
16 ) 0 3

The counter ends at 0, as it must for a valid string, and the peak of 3 was reached at the bracket directly enclosing the 8.

Complexity. Time O(n): a single pass with constant work per character. Space O(1): two integers.

Only the increments can produce a new maximum, so best is updated inside the ( branch alone. Checking after a decrement is harmless but can never change the answer.

Edge cases and pitfalls