DSA problem
Maximum Nesting Depth of the Parentheses
A string is a valid parentheses string (denoted VPS) if it meets one of the following: it is an empty string "", or a single character not equal to "(" or ")", or it can be written as AB (A concatenated with B), where A and B are VPS's, or it can be written as (A), where A is a VPS.
The nesting depth depth(S) of any VPS S is defined recursively: depth("") is 0, depth(C) is 0 for any single non-parenthesis character C, depth(A + B) = max(depth(A), depth(B)), and depth("(" + A + ")") = 1 + depth(A).
Given a VPS represented as string s, return the maximum nesting depth of s. Intuitively this is the deepest level of nested parentheses encountered while scanning the string left to right.
A literal "use a stack" solution would push on '(' and pop on ')', tracking the maximum stack size. That works in O(n) time and O(n) space. The optimal observation is that, because the input is a valid VPS, the stack only ever contains '(' characters — so we don't actually need the stack at all. A single integer depth acting as a "stack height" counter, incremented on '(' and decremented on ')', tracks the same information in O(1) extra space.
Examples
s = "(1+(2*3)+((8)/4))+1"3s = "(1)+((2))+(((3)))"3s = "1+(2*3)/(2-1)"1Constraints
- 1 <= s.length <= 100
- s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
- It is guaranteed that the parentheses in s form a VPS.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.