algoadvance

Given a string s representing a valid parentheses string, return the maximum nesting depth of the parentheses.

A valid parentheses string is defined as follows:

1. "" (an empty string) is a valid parentheses string.
2. s is a valid parentheses string if s is formed by concatenation of two valid parentheses strings.
3. s is a valid parentheses string if s is formed by wrapping a valid parentheses string with a pair of parentheses.

The nesting depth of "((()))" is 3, while the nesting depth of "()(())" is 2.

Clarifying Questions

1. Can the input string contain any characters other than parentheses?
   • No, the input string only contains '(' and ')'.
2. Can the input string be empty?
   • Yes, an empty string is a valid input and its maximum depth would be 0.
3. Are we interested in counting nested structures only or all parentheses?
   • We are interested in the maximum nesting depth, which refers to the deepest level of nested parentheses.

Code

def maxDepth(s: str) -> int:
    max_depth = 0
    current_depth = 0

    for char in s:
        if char == '(':
            current_depth += 1
            if current_depth > max_depth:
                max_depth = current_depth
        elif char == ')':
            current_depth -= 1
    
    return max_depth

# Example usage:
input_string = "((()))"
print(maxDepth(input_string))  # Output: 3

Strategy

1. Initialize Variables: Create variables max_depth and current_depth to keep track of the maximum nesting depth observed and the current depth respectively.
2. Iterate through the String: Loop through each character in the string.
   • If the character is '(', increment the current_depth by 1.
   • Update max_depth if the current_depth is greater than max_depth.
   • If the character is ')', decrement the current_depth by 1.
3. Return the Result: After iterating through the string, the value of max_depth will be the maximum nesting depth.

Time 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 a fixed amount of extra space for the max_depth and current_depth variables, regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?