We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Nesting Depth of the Parentheses

Number: 1737

Difficulty: Easy

Paid? No

Companies: Bloomberg, Meta, Amazon, Microsoft, Google, Intel

Problem Description

Given a valid parentheses string s (along with digits and operators), return the nesting depth of s. The nesting depth is defined as the maximum number of nested parentheses within the expression.

Key Insights

  • Use a counter to track the current nesting level.
  • Increment the counter when encountering an opening parenthesis '('.
  • Update the maximum depth if the current counter exceeds the previous maximum.
  • Decrement the counter when encountering a closing parenthesis ')'.
  • Since the input is guaranteed to be a valid parentheses string, no additional checks are required.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1)

Solution

The approach involves iterating over every character in the string once. We maintain two variables: one to count the current level of nesting (currentDepth) and one to store the maximum depth encountered (maxDepth). For every character:

  • If it is an opening parenthesis '(', increment currentDepth. Then check and update maxDepth if currentDepth is greater.
  • If it is a closing parenthesis ')', decrement currentDepth. This simple counter approach ensures that we determine the maximum nesting depth efficiently using constant extra space.

Code Solutions

# Function to calculate the maximum nesting depth of the parentheses in the string
def maxDepth(s: str) -> int:
    currentDepth = 0  # To keep track of current nesting level
    maxDepth = 0      # To record the maximum nesting depth encountered
    
    # Iterate over each character in the string s
    for char in s:
        if char == '(':
            currentDepth += 1       # Increase nesting level for '('
            maxDepth = max(maxDepth, currentDepth)  # Update maxDepth if needed
        elif char == ')':
            currentDepth -= 1       # Decrease nesting level for ')'
    return maxDepth

# Example usage
s = "(1+(2*3)+((8)/4))+1"
print(maxDepth(s))  # Output: 3
← Back to All Questions