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
- Keep a stack of string buffers, one per nesting level.
- On
(, push a new empty buffer. On), pop the innermost buffer, reverse it, and append it to the enclosing buffer. - Letters are appended to the current (topmost) buffer.
- 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.