Explorer
Data Structures & Algorithms

Find maximum nesting depth of parentheses in a string.

Problem Statement

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

Examples

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

Output: 3

Explanation: Combining the input according to Maximum Nesting Depth of the Parentheses logic yields 3.

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

Output: 3

Explanation: Combining the input according to Maximum Nesting Depth of the Parentheses logic yields 3.

Complexity

Time Complexity: O(N)

Space Complexity: O(1)

Hints

šŸ’” Hint 1: Iterate through the string and ignore all characters other than ( and ). šŸ’” Hint 2: Increment current depth on (, decrement on ). šŸ’” Hint 3: Track the maximum current depth reached at any point.

Editorial & Approach

Problem Overview & Intuition

The nesting depth corresponds to the maximum number of unmatched opening parentheses at any point in a valid parentheses string. A simple counter tracking the current depth in a single linear scan is optimal.

Step-by-Step Approach

  1. Initialize maxD = 0 and currentD = 0.
  2. For each character c in s:
  3. If c === "(", currentD++ and update maxD = Math.max(maxD, currentD).
  4. If c === ")", currentD--.
  5. Return maxD.

Optimal Implementation (JavaScript)

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

Complexity Analysis

Time Complexity O(N) ā€” single pass through string.
Space Complexity O(1) ā€” constant extra variables.

Edge Cases & Corner Traps Handled

  • No parentheses in string: depth is 0.
  • Flat parentheses "()()()": depth is 1.
  • Deeply nested "(((())))": depth is 4.

Maximum Nesting Depth of the Parentheses

Medium
Given a valid parentheses string `s`, return the nesting depth of `s`. The nesting depth is the maximum number of nested parentheses.
Example Scenarios
1Example 1
Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation:

Combining the input according to Maximum Nesting Depth of the Parentheses logic yields 3.

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

Combining the input according to Maximum Nesting Depth of the Parentheses logic yields 3.

Editor
Loading Editor...
s =
"(1+(2*3)+((8)/4))+1"
Output:Click "Run" above to execute and verify your code here.
3