⚡Flashcard Drill➔
NeetCode #362LC-1190MediumStack
← Back to All Problems

#362 · #1190 · Reverse Substrings Between Each Pair of Parentheses(反转每对括号间的子串)

📌 Problem Statement & Constraints

You are given a string s consisting of lowercase letters and parentheses. Reverse the substrings inside each pair of matching parentheses, starting from the innermost pair, and return the result. Constraints: 1 <= s.length <= 2000; the input is always valid.

💡 Core Algorithmic Approaches

  1. Keep a stack of string buffers, one per nesting level.
  2. On (, push a new empty buffer. On ), pop the innermost buffer, reverse it, and append it to the enclosing buffer.
  3. Letters are appended to the current (topmost) buffer.
  4. This resolves nesting automatically, because inner levels are reversed before being merged outward.

💻 Benchmark Python3 Implementation

class Solution:
    def reverseParentheses(self, s: str) -> str:
        st = [[]]                          # one buffer per nesting level
        for ch in s:
            if ch == "(":
                st.append([])              # enter a new level
            elif ch == ")":
                inner = st.pop()[::-1]     # reverse the completed level
                st[-1].extend(inner)
            else:
                st[-1].append(ch)
        return "".join(st[0])

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2) worst case, because reversing nested levels can copy the same characters repeatedly (depth d means up to d passes over each character).
💾 Space Complexity
O(n) for the buffers.

⚠️ Interview Pitfalls & Follow-ups

  • Reversing before popping: the order is pop, then reverse, then extend into the parent.
  • Forgetting to start with an outer buffer: the top-level characters need somewhere to go.
  • Trying to find matching parentheses with a stack of indices: workable, but the buffer stack is much shorter to write and just as clear.
  • Reversing the whole string at the end: only the parenthesised substrings are reversed, and they nest.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Stack Problems