Deepest Nesting Level

EasyStack

Problem

A formula s contains letters, digits, operators and well-formed parentheses. The nesting level of a character is the number of parenthesis pairs that enclose it.

Return the maximum nesting level reached anywhere in s (0 if there are no parentheses).

Example 1

Input:
s = "a(b(c)d)(e)"
Output:
2

c sits inside two pairs.

Example 2

Input:
s = "xyz"
Output:
0

Constraints

  • 0 ≤ s.length ≤ 10^5
  • The parentheses in s are balanced

Hint

Show the first hint

If you pushed every '(' on a stack and popped on ')', what would the stack size mean?

Walkthrough

How to approach it

01Clarify before coding

  • Are the parentheses guaranteed balanced? Yes, so no validation is needed.
  • Do other bracket kinds count? No, only '(' and ')'.

02Brute force

For every character, count how many '(' before it are still open by rescanning the prefix.

Cost: O(n²) time for 10^5 characters.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.