Maximum Nesting Depth of the Parentheses — Solution
Maximum Nesting Depth of the Parentheses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Maximum Nesting Depth of the Parentheses is an easy coding problem on strings and stack, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Strings, Stack
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a valid parentheses string s — a string of digits, +, -, *, / and balanced parentheses — return the maximum nesting depth of its parentheses.
The nesting depth of a string with no parentheses is 0.
Example 1
Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation: The 8 sits three levels deep.
Example 2
Input: s = "(1)+((2))+(((3)))"
Output: 3
Example 3
Input: s = "1+2"
Output: 0
Constraints
1 <= s.length <= 40s is a valid parentheses string.
Hints for Maximum Nesting Depth of the Parentheses
Hint 1
No stack is needed — only the stack's height matters.
Hint 2
Increment a counter on
(, decrement on), and record the largest value the counter ever reaches.
How to solve Maximum Nesting Depth of the Parentheses
Only the stack's height matters: count up on (, down on ), and remember the peak.
Approach
- Set
depth = best = 0. - For
(, incrementdepthand updatebest; for), decrement. - Return
best.
Why it works
In a valid parentheses string the running counter equals the number of currently open brackets, and the maximum value it takes is the deepest nesting.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Digits and operators are ignored entirely.
- A string with no parentheses returns 0 naturally.
Reference solution
Python
def maxDepth(s: str) -> int:
depth = best = 0
for ch in s:
if ch == "(":
depth += 1
if depth > best:
best = depth
elif ch == ")":
depth -= 1
return bestJava
public static int maxDepth(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;
}C++
int maxDepth(string s) {
int depth = 0, best = 0;
for (char c : s) {
if (c == '(') {
depth++;
if (depth > best) best = depth;
} else if (c == ')') {
depth--;
}
}
return best;
}JavaScript
var maxDepth = function(s) {
let depth = 0, best = 0;
for (let i = 0; i < s.length; i++) {
if (s[i] === "(") {
depth++;
if (depth > best) best = depth;
} else if (s[i] === ")") {
depth--;
}
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Stack Data Structure