{x}
blog image

Maximum Nesting Depth of the Parentheses

Given a valid parentheses string s, return the nesting depth of s. The nesting depth is the maximum number of nested parentheses.

 

Example 1:

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

Output: 3

Explanation:

Digit 8 is inside of 3 nested parentheses in the string.

Example 2:

Input: s = "(1)+((2))+(((3)))"

Output: 3

Explanation:

Digit 3 is inside of 3 nested parentheses in the string.

Example 3:

Input: s = "()(())((()()))"

Output: 3

 

Constraints:

  • 1 <= s.length <= 100
  • s consists of digits 0-9 and characters '+', '-', '*', '/', '(', and ')'.
  • It is guaranteed that parentheses expression s is a VPS.

Solution Explanation for Maximum Nesting Depth of Parentheses

This problem asks us to find the maximum nesting depth of parentheses in a given valid parentheses string. The solution leverages a simple linear traversal approach.

Approach:

We initialize two variables:

  • ans: This variable stores the maximum nesting depth encountered so far. It's initialized to 0.
  • d: This variable tracks the current nesting depth. It's also initialized to 0.

The algorithm iterates through the input string s character by character:

  1. Opening Parenthesis (: If the current character is an opening parenthesis, we increment d (increase the nesting depth) and update ans to be the maximum of ans and d. This ensures ans always holds the highest nesting depth seen.

  2. Closing Parenthesis ): If the current character is a closing parenthesis, we decrement d (decrease the nesting depth). We don't need to update ans here because the maximum depth is already recorded when encountering the corresponding opening parenthesis.

  3. Other Characters: Characters other than '(' and ')' are ignored because they don't affect the nesting depth.

After iterating through the entire string, ans will contain the maximum nesting depth.

Time and Space Complexity:

  • Time Complexity: O(n), where n is the length of the input string. We iterate through the string once.
  • Space Complexity: O(1). We use only a few constant extra variables (ans and d).

Code Examples (with explanations):

Python:

class Solution:
    def maxDepth(self, s: str) -> int:
        ans = d = 0  # Initialize max depth (ans) and current depth (d) to 0
        for c in s:  # Iterate through the string
            if c == '(':  # If it's an opening parenthesis
                d += 1  # Increment current depth
                ans = max(ans, d)  # Update max depth if necessary
            elif c == ')':  # If it's a closing parenthesis
                d -= 1  # Decrement current depth
        return ans  # Return the maximum depth

Java:

class Solution {
    public int maxDepth(String s) {
        int ans = 0, d = 0; // Initialize max depth (ans) and current depth (d) to 0
        for (int i = 0; i < s.length(); ++i) { // Iterate through the string
            char c = s.charAt(i);
            if (c == '(') { // If it's an opening parenthesis
                ans = Math.max(ans, ++d); // Increment current depth and update max depth
            } else if (c == ')') { // If it's a closing parenthesis
                --d; // Decrement current depth
            }
        }
        return ans; // Return the maximum depth
    }
}

C++:

class Solution {
public:
    int maxDepth(string s) {
        int ans = 0, d = 0; // Initialize max depth (ans) and current depth (d) to 0
        for (char& c : s) { // Iterate through the string
            if (c == '(') { // If it's an opening parenthesis
                ans = max(ans, ++d); // Increment current depth and update max depth
            } else if (c == ')') { // If it's a closing parenthesis
                --d; // Decrement current depth
            }
        }
        return ans; // Return the maximum depth
    }
};

The other languages (Go, TypeScript, Javascript, C#) follow a very similar structure, differing only in syntax. The core logic remains the same efficient linear traversal.