💬 Discord
Sign In
NeetCode #766LC-1614EasyGreedy
← Back to All Problems

#766 · #1614 · Maximum Nesting Depth of the Parentheses(括号的最大嵌套深度)

📌 Problem Statement & Constraints

A string s is a valid parentheses string (VPS) if it is empty, or (A) or AB for VPS A and B, and contains no other characters. Return the maximum nesting depth of the parentheses. Constraints: 1 <= s.length <= 100.

💡 Core Algorithmic Approaches

  1. Track the current depth: increment on ( and decrement on ).
  2. The answer is the maximum depth ever reached.
  3. Digits and operators in the string are ignored because they do not affect nesting.
  4. Because the string is a VPS, the depth never goes negative and ends at 0.

💻 Benchmark Python3 Implementation

class Solution:
    def maxDepth(self, s: str) -> int:
        depth = 0
        best = 0
        for c in s:
            if c == "(":
                depth += 1
                best = max(best, depth)
            elif c == ")":
                depth -= 1
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass.
💾 Space Complexity
O(1): two counters.

⚠️ Interview Pitfalls & Follow-ups

  • Counting digits or operators as nesting: only parentheses affect the depth.
  • Updating best on ) instead of (: the depth peaks just after an opening bracket, so record it there.
  • Returning the final depth: the final depth is always 0 for a valid string, not the maximum.
  • Decrementing before the depth check: the order matters only for (, where the increment precedes the maximum update.