LeetCode Problem 1614

Difficulty: 🟢 Easy
Topics: String, Stack

Solution

LeetCode 1614, Maximum Nesting Depth of the Parentheses

Problem Understanding

This problem asks us to compute the maximum nesting depth of parentheses in a valid parentheses string.

A valid parentheses string, often abbreviated as VPS, is a string where every opening parenthesis '(' has a matching closing parenthesis ')', and the parentheses are properly balanced. The string may also contain digits and arithmetic operators, but only the parentheses affect the nesting depth.

The nesting depth refers to how deeply parentheses are nested inside one another. For example:

• "()" has depth 1
• "(())" has depth 2
• "((()))" has depth 3

The goal is to scan the string and determine the largest number of simultaneously open parentheses at any point.

For the input:

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

the digit 8 lies inside three nested pairs of parentheses, so the answer is 3.

The constraints are very small:

• 1 <= s.length <= 100
• The string is guaranteed to be valid

These constraints tell us that performance is not a major issue, but we should still design a clean and efficient solution. Since the string is guaranteed to be valid, we do not need to handle malformed expressions or unmatched parentheses.

Several edge cases are important to keep in mind:

• Strings with no nesting, such as "()", should return 1
• Strings with deep nesting, such as "(((())))", should correctly count every level
• Strings containing many non-parenthesis characters should ignore them completely
• Sequential groups like "()()()" should not increase nesting depth beyond 1
• An empty current depth after processing closing parentheses should never go negative because the input is guaranteed valid

Approaches

Brute Force Approach

A brute force solution would examine every position in the string and determine how deeply nested that position is.

One way to do this is:

• For every character in the string:

• Count how many unmatched opening parentheses exist before that position

• Track the maximum count encountered

This works because the nesting depth at any point equals the number of currently open parentheses.

However, recalculating the nesting depth from scratch for every character leads to repeated work. If the string length is n, and we scan part of the string for every position, the total complexity becomes O(n^2).

Although the constraints are small enough that this would still pass, it is inefficient and unnecessary.

Optimal Approach

The key observation is that we do not need to repeatedly recompute nesting depth.

Instead, we can process the string once from left to right while maintaining:

• current_depth, the number of currently open parentheses
• max_depth, the largest depth seen so far

When we encounter '(':

• Increase current_depth
• Update max_depth if needed

When we encounter ')':

• Decrease current_depth

All other characters are ignored because they do not affect nesting.

This works because the current nesting depth at any point is exactly the number of unmatched opening parentheses encountered so far.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Recomputes nesting depth repeatedly
Optimal	O(n)	O(1)	Single pass while tracking current depth

Algorithm Walkthrough

1. Initialize two variables:

• current_depth = 0
• max_depth = 0

The current_depth variable tracks how many opening parentheses are currently active. The max_depth variable stores the largest depth encountered during traversal. 2. Traverse the string character by character.

We process each character exactly once because the nesting information can be maintained incrementally. 3. If the current character is '(':

• Increment current_depth by 1

• Update max_depth with the larger of:

• current max_depth

• current current_depth

This reflects entering a deeper nesting level. 4. If the current character is ')':

• Decrement current_depth by 1

This reflects exiting one level of nesting. 5. Ignore all other characters.

Digits and operators do not affect nesting structure. 6. After processing the entire string, return max_depth.

Why it works

At every position in the string, current_depth equals the number of opening parentheses that have not yet been closed. This is precisely the definition of the current nesting level. Since max_depth stores the maximum value that current_depth ever reaches, it must equal the maximum nesting depth of the entire expression.

Python Solution

class Solution:
    def maxDepth(self, s: str) -> int:
        current_depth = 0
        max_depth = 0

        for char in s:
            if char == "(":
                current_depth += 1
                max_depth = max(max_depth, current_depth)
            elif char == ")":
                current_depth -= 1

        return max_depth

The implementation follows the exact algorithm described earlier.

The variable current_depth tracks the active nesting level while traversing the string. Every opening parenthesis increases the depth because we are entering a deeper level of nesting. Immediately after incrementing, we compare against max_depth to record the highest level reached so far.

When a closing parenthesis is encountered, we reduce current_depth because one nested level has ended.

Characters such as digits and arithmetic operators are ignored automatically because they do not satisfy either condition.

Since the string is guaranteed to be valid, current_depth never becomes negative during traversal.

Go Solution

func maxDepth(s string) int {
    currentDepth := 0
    maxDepth := 0

    for _, char := range s {
        if char == '(' {
            currentDepth++

            if currentDepth > maxDepth {
                maxDepth = currentDepth
            }
        } else if char == ')' {
            currentDepth--
        }
    }

    return maxDepth
}

The Go implementation mirrors the Python solution closely.

Go uses rune values during string iteration with range, so comparisons are made against character literals like '(' and ')'.

No additional data structures are required, and integer overflow is not a concern because the maximum string length is only 100.

Worked Examples

Example 1

Input:

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

Character	Action	current_depth	max_depth
(	Open parenthesis	1	1
1	Ignore	1	1
+	Ignore	1	1
(	Open parenthesis	2	2
2	Ignore	2	2
*	Ignore	2	2
3	Ignore	2	2
)	Close parenthesis	1	2
+	Ignore	1	2
(	Open parenthesis	2	2
(	Open parenthesis	3	3
8	Ignore	3	3
)	Close parenthesis	2	3
/	Ignore	2	3
4	Ignore	2	3
)	Close parenthesis	1	3
)	Close parenthesis	0	3
+	Ignore	0	3
1	Ignore	0	3

Final answer:

3

Example 2

Input:

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

Character	Action	current_depth	max_depth
(	Open	1	1
1	Ignore	1	1
)	Close	0	1
+	Ignore	0	1
(	Open	1	1
(	Open	2	2
2	Ignore	2	2
)	Close	1	2
)	Close	0	2
+	Ignore	0	2
(	Open	1	2
(	Open	2	2
(	Open	3	3
3	Ignore	3	3
)	Close	2	3
)	Close	1	3
)	Close	0	3

Final answer:

3

Example 3

Input:

"()(())((()()))"

Character	Action	current_depth	max_depth
(	Open	1	1
)	Close	0	1
(	Open	1	1
(	Open	2	2
)	Close	1	2
)	Close	0	2
(	Open	1	2
(	Open	2	2
(	Open	3	3
)	Close	2	3
(	Open	3	3
)	Close	2	3
)	Close	1	3
)	Close	0	3

Final answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once
Space	O(1)	Only two integer variables are used

The algorithm performs a single pass through the input string. Each character requires constant work, so the total runtime grows linearly with the string length.

The memory usage remains constant regardless of input size because no auxiliary data structures are allocated.

Test Cases

solution = Solution()

assert solution.maxDepth("(1+(2*3)+((8)/4))+1") == 3  # mixed operators and nested parentheses
assert solution.maxDepth("(1)+((2))+(((3)))") == 3  # increasing nesting groups
assert solution.maxDepth("()(())((()()))") == 3  # multiple separate nested sections

assert solution.maxDepth("()") == 1  # smallest non-empty valid parentheses
assert solution.maxDepth("(())") == 2  # simple nested structure
assert solution.maxDepth("((()))") == 3  # deeper nesting

assert solution.maxDepth("()()()") == 1  # sequential groups without nesting
assert solution.maxDepth("(((())))") == 4  # deeply nested parentheses
assert solution.maxDepth("(1)+((2*3)/(4-5))") == 2  # operators and digits mixed in
assert solution.maxDepth("1+(2*3)/(2-1)") == 1  # only one nesting level
assert solution.maxDepth("12345") == 0  # no parentheses at all
assert solution.maxDepth("((((((1))))))") == 6  # large nesting depth

Test	Why
"(1+(2*3)+((8)/4))+1"	Validates mixed characters and nested groups
"(1)+((2))+(((3)))"	Validates multiple independent nesting depths
"()(())((()()))"	Validates combined sequential and nested structures
"()"	Smallest valid nested expression
"(())"	Basic nested case
"((()))"	Multiple levels of nesting
"()()()"	Sequential groups should not increase depth
"(((())))"	Deep nesting stress case
"(1)+((2*3)/(4-5))"	Digits and operators intermixed
"1+(2*3)/(2-1)"	Only shallow nesting
"12345"	No parentheses at all
"((((((1))))))"	Large continuous nesting depth

Edge Cases

One important edge case is a string with no parentheses at all, such as "12345". A naive implementation might incorrectly assume that at least one parenthesis exists and return 1. The correct answer is 0 because there is no nesting. The implementation handles this naturally because current_depth and max_depth never increase.

Another important case is sequential parentheses groups such as "()()()". These groups are not nested inside one another, so the maximum depth should remain 1. An incorrect solution might accidentally count the total number of parenthesis pairs instead of the maximum active nesting level. Since the algorithm increments and decrements depth immediately as groups open and close, it correctly reports 1.

A third important edge case is deeply nested input such as "(((())))". This case ensures that the implementation correctly tracks increasing depth over several levels. The algorithm updates max_depth immediately after every opening parenthesis, guaranteeing that the deepest level is recorded accurately.

Another subtle case involves non-parenthesis characters interspersed throughout the expression, such as "(1+(2*3)-4)". Digits and operators should not affect nesting depth. The implementation explicitly checks only for '(' and ')', so all other characters are safely ignored.