Maximum nesting depth of the Parentheses

Problem Link

1614. Maximum Nesting Depth of the Parentheses – LeetCode

Problem Statement

You are given a valid parentheses string (VPS) s, composed of:

• digits (0-9)

• operators (+, -, *, /)

• parentheses ( and )

Your task is to compute the maximum nesting depth of parentheses in the string.

Nesting depth is defined as the maximum number of open parentheses at any point.

Examples

Example 1:

Input: s = "(1+(2*3)+((8)/4))+1"
Output: 3
Explanation: The digit `8` is inside 3 levels of nested parentheses.

Example 2:

Input: s = "(1)+((2))+(((3)))"
Output: 3
Explanation: The digit `3` is inside 3 levels of nesting.

Example 3:

Input: s = "()(())((()()))"
Output: 3

Constraints

• 1 <= s.length <= 100

• s consists of digits 0-9, operators +, -, *, /, and parentheses ( and )

• It is guaranteed that s is a valid parentheses string (VPS)

Intuition

We need to count how deep the parentheses go:

• Every time we see '(', we are going deeper → increase current depth

• Every time we see ')', we are coming out of a level → decrease current depth

• Track the maximum value that depth reaches during this traversal

This is a classic depth tracking problem — no stack is needed because we only care about the count, not the structure.

Approach

1. Initialize:

   • cnt = 0 → current depth

   • max = 0 → maximum depth observed

2. Iterate through each character:

   • If '(': increment cnt and update max

   • If ')': decrement cnt

   • Else: skip (not a parenthesis)

3. Return max

Java Code

class Solution {
    public int maxDepth(String s) {
        int cnt = 0;
        int max = 0;

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                cnt++;
                max = Math.max(max, cnt);
            } else if (ch == ')') {
                cnt--;
            }
        }

        return max;
    }
}

Time and Space Complexity

• We traverse the string once.

• No additional space is used apart from integer counters.

Dry Run

Input: s = "(1+(2*3)+((8)/4))+1"

Iterating:
(  → cnt = 1 → max = 1  
1  → skip  
+  → skip  
(  → cnt = 2 → max = 2  
2  → skip  
*  → skip  
3  → skip  
)  → cnt = 1  
+  → skip  
(  → cnt = 2  
(  → cnt = 3 → max = 3  
8  → skip  
)  → cnt = 2  
/  → skip  
4  → skip  
)  → cnt = 1  
)  → cnt = 0  
+  → skip  
1  → skip  

Result: `max = 3`

Conclusion

This problem is a clean application of a depth counter for nested structures. You can use the same principle in:

• Parsing expressions

• Analyzing XML/HTML tag nesting

• Balancing brackets

Always remember:

• '(' → increase depth

• ')' → decrease depth

• Keep track of the maximum during traversal