Domain 1EasyCORE

Maximum Nesting Depth of the Parentheses

The problem requires us to determine the maximum nesting depth of parentheses in a given valid parentheses string (VPS). A VPS is defined by specific rules involving concatenation and wrapping with parentheses. The input is a string `s` that represents a VPS, and the output should be an integer representing the maximum depth of nested parentheses.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

1614. Maximum Nesting Depth of the Parentheses

Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 1
Acceptance rate: 82.7%


Problem Breakdown

The problem requires us to determine the maximum nesting depth of parentheses in a given valid parentheses string (VPS). A VPS is defined by specific rules involving concatenation and wrapping with parentheses. The input is a string s that represents a VPS, and the output should be an integer representing the maximum depth of nested parentheses.

Inputs:

  • A string s consisting of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.

Outputs:

  • An integer representing the maximum nesting depth of the parentheses in the string.

Implicit Constraints or Tricky Edge Cases:

  • The input string is guaranteed to be a VPS, so we don’t need to handle invalid strings.
  • The string can contain no parentheses, resulting in a depth of 0.
  • The string length is between 1 and 100 characters.

Intuition

To solve this problem, we need to traverse the string and keep track of the current depth of nested parentheses. A brute-force approach would involve checking every possible substring to determine its depth, which would be inefficient with a time complexity of O(n^2). Instead, we can use a single pass through the string while maintaining a counter for the current depth.

The key insight is that each opening parenthesis ( increases the depth by 1, and each closing parenthesis ) decreases the depth by 1. By keeping track of these changes, we can determine the maximum depth encountered during the traversal.

Approach

We will use a single pass through the string to calculate the maximum nesting depth. We’ll maintain two variables:

  • current_depth: To keep track of the current level of nested parentheses.
  • max_depth: To store the maximum depth encountered so far.

As we iterate through the string:

  1. If we encounter an opening parenthesis (, we increment current_depth.
  2. If we encounter a closing parenthesis ), we decrement current_depth.
  3. After updating current_depth for each parenthesis, we update max_depth if current_depth is greater than the current max_depth.

This approach ensures that we efficiently compute the maximum depth in linear time.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. We make a single pass through the string.
  • Space Complexity: O(1). We use only a constant amount of extra space for the current_depth and max_depth variables.

Solution

def maxDepth(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

Edge Cases Handled

  • Empty Input: If the input string is empty (""), the function returns 0, as there are no parentheses to nest.
  • No Parentheses: If the string contains no parentheses (e.g., "123"), the function correctly returns 0.
  • Single Pair of Parentheses: For strings like "(1)", the function returns 1, indicating a single level of nesting.
  • Multiple Levels of Nesting: The function handles multiple levels of nested parentheses, such as "((()))", returning the correct depth of 3.