Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Example 1

Input

(1+(2*3)+((8)/4))+1

Output

3

Example 2

Input

(1)+((2))+(((3)))

Output

3

Hints

  1. You only need to count — no stack required.
  2. 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