Practice › Strings
Maximum Nesting Depth of Parentheses
Easy · Strings · Asked at Amazon, Bloomberg, TCS, Infosys
The string is a valid expression made of digits, + - * / and parentheses. Print its maximum nesting depth — the largest number of parentheses open at the same time.
Input
A single string s (no spaces).
Output
The maximum depth.
Constraints
- 1 ≤ |s| ≤ 10^5
- The parentheses in
sare balanced
Example 1
Input
(1+(2*3)+((8)/4))+1
Output
3
Example 2
Input
(1)+((2))+(((3)))
Output
3
Hints
- You only need to count — no stack required.
- Increase a counter on "(", decrease it on ")", and remember the largest value it reaches.
Approach
Because the parentheses are balanced, the number of currently open brackets is just a counter. Track its maximum while scanning; digits and operators are ignored.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int d = 0, best = 0;
for (char c : s) {
if (c == '(') best = max(best, ++d);
else if (c == ')') d--;
}
cout << best << "\n";
return 0;
}Python solution
s = input().strip()
d = best = 0
for c in s:
if c == "(":
d += 1
best = max(best, d)
elif c == ")":
d -= 1
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
String s = new Scanner(System.in).next();
int d = 0, best = 0;
for (char c : s.toCharArray()) {
if (c == '(') best = Math.max(best, ++d);
else if (c == ')') d--;
}
System.out.println(best);
}
}Solve Maximum Nesting Depth of Parentheses online · All practice problems