Maximum Nesting Depth of the Parentheses

Difficulty: Easy | Acceptance: 84.90% | Paid: No Topics: String, Stack

A string is a valid parentheses string (denoted VPS) if it meets one of the following:

It is an empty string "", or a single character not equal to ”(” or ”)”, It can be written as AB (A concatenated with B), where A and B are VPS’s, or It can be written as (A), where A is a VPS. We can similarly define the nesting depth depth(S) of any VPS S as follows:

depth("") = 0 depth(C) = 0, where C is a string with a single character not equal to ”(” or ”)”. depth(A + B) = max(depth(A), depth(B)), where A and B are VPS’s. depth(”(” + A + ”)”) = 1 + depth(A), where A is a VPS. For example, "", ”()()”, and ”()(()())” are VPS’s (with nesting depths 0, 1, and 2), and ”)(” and ”(()” are not VPS’s.

Given a VPS represented as string s, return the maximum nesting depth of s.

• Examples
• Constraints
• Approach 1: Counter
• Approach 2: Stack

Examples

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

Input: s = "(1+(2*3)/2)"
Output: 1
Explanation:
The digit 2 is inside of 1 nested parentheses in the string.

Input: s = "1+(2*3)/(2-1)"
Output: 1

Constraints

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

Approach 1: Counter

Intuition Since the input string is guaranteed to be a valid parentheses string (VPS), we do not need to explicitly store the opening brackets to match them later. We can simply iterate through the string and maintain a counter representing the current depth.

Steps

• Initialize currentDepth and maxDepth to 0.
• Iterate through each character in the string.
• If the character is ’(’, increment currentDepth and update maxDepth if currentDepth is greater.
• If the character is ’)’, decrement currentDepth.
• Return maxDepth.

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

Complexity

• Time: O(n), where n is the length of the string. We traverse the string once.
• Space: O(1). We only use a few integer variables for counting.
• Notes: This is the most optimal solution for this problem.

Approach 2: Stack

Intuition We can simulate the nesting structure using a stack. Every time we encounter an opening parenthesis ’(’, we push it onto the stack. The size of the stack at any point represents the current nesting depth.

Steps

• Initialize an empty stack and maxDepth to 0.
• Iterate through each character in the string.
• If the character is ’(’, push it onto the stack and update maxDepth with the stack size.
• If the character is ’)’, pop the top element from the stack.
• Return maxDepth.

class Solution:
    def maxDepth(self, s: str) -> int:
        stack = []
        max_depth = 0
        for char in s:
            if char == '(':
                stack.append(char)
                max_depth = max(max_depth, len(stack))
            elif char == ')':
                stack.pop()
        return max_depth

Complexity

• Time: O(n), where n is the length of the string. We process each character once.
• Space: O(n), in the worst case where the string consists of all opening parentheses, the stack will grow to size n.
• Notes: While conceptually clear, this uses more memory than the counter approach.