Leetcode – Maximum Nesting Depth of the Parentheses Solution

Spread the love

In computer science, string manipulation and stack data structure are often encountered concepts. One of the popular problems that utilize both is the “Maximum Nesting Depth of the Parentheses” problem from Leetcode. This problem serves as an excellent exercise for beginners and seasoned developers alike to sharpen their algorithmic skills.

In this exhaustive article, we will delve deep into the problem description, discuss multiple approaches to solve it, understand their time and space complexity, and finally, implement them in Python. Along the way, we will also discuss some related problems and insights that can be derived from this problem.

Problem Description

The problem description on Leetcode is as follows:

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

  • It is an empty string "", 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(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 string s, return the nesting depth of s.

Examples

maxDepth("(1+(2*3)+((8)/4))+1") # Output: 3
maxDepth("(1)+((2))+(((3)))")   # Output: 3
maxDepth("1+(2*3)/(2-1)")       # Output: 1
maxDepth("1")                   # Output: 0

Approach 1: Stack-Based Solution

Algorithm

  1. Initialize an empty stack and a variable max_depth to keep track of the maximum depth.
  2. Iterate through each character in the string s.
    • If the character is '(', push it onto the stack and update max_depth with the current stack size if the stack size is greater than max_depth.
    • If the character is ')', pop the top element from the stack.
  3. Return max_depth.

Python Code

def maxDepth(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

Time Complexity

The time complexity of this approach is O(n), where n is the length of the string s.

Space Complexity

The space complexity is also O(n) due to the stack used for storing elements.

Approach 2: Constant Space Solution

Algorithm

  1. Initialize two variables current_depth and max_depth to 0.
  2. Iterate through each character in the string s.
    • If the character is '(', increment current_depth by 1 and update max_depth if current_depth is greater than max_depth.
    • If the character is ')', decrement current_depth by 1.
  3. Return max_depth.

Python Code

def maxDepth(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

Time Complexity

The time complexity is O(n), where n is the length of the string s.

Space Complexity

The space complexity is O(1) as we are not using any extra data structures.

Conclusion

Both approaches are quite efficient, but the second approach is slightly better in terms of space complexity. Understanding this problem not only tests your knowledge of stack data structures and string manipulation but also sets the foundation for more complex problems like parsing arithmetic expressions and evaluating them.

Leave a Reply