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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Nesting Depth of the Parentheses

Difficulty: Easy

Problem Description

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

Key Insights

  • The problem requires finding the maximum depth of nested parentheses in a valid string.
  • Each opening parenthesis '(' increases the current depth, while each closing parenthesis ')' decreases it.
  • We can keep track of the current depth and update the maximum depth whenever we encounter an opening parenthesis.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string s. Space Complexity: O(1), since we only use a few variables to track depth and maximum depth.

Solution

To solve this problem, we can use a simple iterative approach where we traverse the string character by character. We will maintain a variable to track the current depth of parentheses and another variable to track the maximum depth encountered during the traversal. When we encounter an opening parenthesis '(', we increment the current depth. When we encounter a closing parenthesis ')', we decrement the current depth. At each increment, we will check if the current depth exceeds the maximum depth and update it accordingly.

Code Solutions

def maxDepth(s: str) -> int:
    max_depth = 0  # Variable to track the maximum depth
    current_depth = 0  # Variable to track the current depth

    for char in s:
        if char == '(':  # If we find an opening parenthesis
            current_depth += 1  # Increase current depth
            max_depth = max(max_depth, current_depth)  # Update max depth if needed
        elif char == ')':  # If we find a closing parenthesis
            current_depth -= 1  # Decrease current depth

    return max_depth  # Return the maximum depth found
← Back to All Questions