1614. Maximum Nesting Depth of the Parentheses - Explanation

Problem Link

Description

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

Example 1:

Input: s = "(1+(2*3)+((8)/4))+1"

Output: 3

Explanation: Digit 8 is inside of 3 nested parentheses in the string.

Example 2:

Input: s = "(1)+((2))+(((3)))"

Output: 3

Explanation: Digit 3 is inside of 3 nested parentheses in the string.

Example 3:

Input: s = "()(())((()()))"

Output: 3

Constraints:

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Recursion

class Solution:
    def maxDepth(self, s: str) -> int:
        res = 0

        def dfs(i):
            nonlocal res
            if i == len(s):
                return 0

            cur = dfs(i + 1)
            if s[i] == '(':
                cur += 1
            elif s[i] == ')':
                cur -= 1

            res = max(res, abs(cur))
            return cur

        dfs(0)
        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$ for recursion stack.

---

2. Stack

class Solution:
    def maxDepth(self, s: str) -> int:
        res, stack = 0, []

        for c in s:
            if c == "(":
                stack.append(c)
                res = max(res, len(stack))
            elif c == ")":
                stack.pop()

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(n)$

---

3. Iteration

class Solution:
    def maxDepth(self, s: str) -> int:
        res = 0
        cur = 0

        for c in s:
            if c == "(":
                cur += 1
            elif c == ")":
                cur -= 1
            res = max(res, cur)

        return res

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$ extra space.