Reverse Substrings Between Each Pair of Parentheses: Inside-Out Stack Pattern

You are given a string s that consists of lower case English letters and parentheses. Reverse the strings in each pair of matching parentheses, starting from the innermost one. Your result should not contain any parentheses.

This is LeetCode 1190: Reverse Substrings Between Each Pair of Parentheses, and it is one of the best problems for understanding how a stack handles nested structure. The idea of resolving inner groups before outer ones comes up in expression evaluation, nested encoding, and recursive parsing problems across the board.

Why this problem matters

Parentheses problems are everywhere in interviews. Valid Parentheses teaches you to match pairs. Decode String teaches you to save and restore context. This problem adds a new twist: you need to reverse the content each time you close a pair, and the reversals compound as nesting gets deeper.

That compounding effect is what makes this problem tricky. Reversing the inner group changes the order of characters, and then the outer reversal flips them again. If you try to think through the final order by hand, it gets confusing fast. But if you let the stack handle each level independently, the logic stays simple.

The key insight

When you see an opening parenthesis (, you know a new group is starting. Push whatever you have built so far onto the stack and start fresh. When you see a closing parenthesis ), the current group is complete. Reverse it, pop the previous context off the stack, and append the reversed group to it.

This is the same "save context on open, restore on close" pattern from Decode String, but instead of repeating the inner string k times, you reverse it once. Each closing parenthesis triggers exactly one reversal, and the stack ensures that inner groups get reversed before outer ones.

The algorithm:

1. Maintain a current string and a stack of strings.
2. For each character in the input:
   • Letter: append it to current.
   • (: push current onto the stack, reset current to empty.
   • ): reverse current, pop the top of the stack, and set current to popped value + reversed current.
3. When done, current holds the answer.

The solution

def reverse_parentheses(s: str) -> str:
    stack = []
    current = []

    for ch in s:
        if ch == '(':
            stack.append(current)
            current = []
        elif ch == ')':
            current.reverse()
            prev = stack.pop()
            prev.extend(current)
            current = prev
        else:
            current.append(ch)

    return ''.join(current)

Let's walk through each branch.

When we see a letter, we append it to current. This builds up the string for the current nesting level one character at a time.

When we see (, we push current onto the stack and reset it. This is the "save context" step. Everything we have accumulated so far at this level gets frozen on the stack while we work on the inner group.

When we see ), we reverse current (the inner group is complete), pop the previous context from the stack, and extend it with the reversed inner group. The extend call appends each character of the reversed inner group to the previous context, so current now holds everything from the outer level combined with the resolved inner level.

Using a list instead of a string for current is a performance choice. Python strings are immutable, so appending to a string creates a new copy each time. Lists let you append in O(1) and only pay for a single join at the end.

Visual walkthrough

Let's trace through "(u(love)i)" step by step. Watch how the stack grows when we enter parentheses and shrinks when we leave, with a reversal happening on each ).

The key moment is Step 8, when the first ) closes the inner pair. We reverse "love" to "evol", pop "u" from the stack, and combine them into "uevol". Then at Step 10, the outer ) reverses "uevoli" to "iloveu", giving us the final answer.

Complexity analysis

Time is O(n^2) in the worst case. Each character is read once in O(n), but the reverse() calls can process up to O(n) characters each time a ) is encountered. With deeply nested parentheses like "(((...)))", each level triggers a reversal of nearly the entire string. There is an O(n) "wormhole" approach using pre-computed jump indices, but the stack solution is more intuitive and sufficient for the problem's constraints (n <= 2000).

Space is O(n). The stack holds at most O(n) characters total across all its entries, and current holds at most O(n) characters. The combined memory never exceeds the length of the input.

The building blocks

1. Stack-based context save and restore

The core pattern: push state when entering a scope, pop and combine when leaving.

if ch == '(':
    stack.append(current)
    current = []
elif ch == ')':
    current.reverse()
    prev = stack.pop()
    prev.extend(current)
    current = prev

This is the same skeleton as Decode String, Basic Calculator, and any problem that resolves nested structures inside-out. The only thing that changes is what you do with the inner result when you pop. In Decode String you repeat it. In Basic Calculator you apply a sign and add. Here you reverse it. The push/pop framework stays the same.

2. In-place list reversal for string building

Using a list instead of a string, and reversing in place:

current = []
current.append(ch)
current.reverse()
''.join(current)

This avoids the O(n) cost of string concatenation on every append. It is a small detail, but in problems where you build and manipulate strings inside loops, switching from strings to lists can turn an O(n^2) solution into something faster. The reverse() call mutates the list directly with no extra allocation.

Edge cases

• No parentheses: "abc" returns "abc". Every character just gets appended to current, the stack is never used.
• Empty parentheses: "a()b" returns "ab". The ( pushes "a", resets current to empty. The ) reverses the empty string (still empty), pops "a", and combines. No harm done.
• Single level: "(abcd)" returns "dcba". One push, one reversal, one pop.
• Deeply nested: "(a(b(c)))". Inner reversal gives "c", next gives "bc" reversed to "cb", then "acb" reversed to "bca". Each level applies one reversal.
• Adjacent groups: "(ab)(cd)" returns "badc". Each pair is independent. The first group reverses to "ba", then the second group reverses to "dc".

From understanding to recall

You have seen how the stack handles nested parentheses: push on open, reverse and pop on close. The logic is clean and the code is short. But can you write the push/pop/reverse flow from scratch in an interview two weeks from now?

The details that trip people up are small. Do you push current before or after resetting it? Do you reverse before popping or after? Do you extend the popped value with current, or the other way around? These are not conceptual misunderstandings. They are recall failures, and they cost time under pressure.

Spaced repetition closes these gaps. You write the solution from memory at increasing intervals. Each repetition locks in the push order, the reverse timing, and the extend direction. After a few rounds, you see "nested parentheses with transformation" in a problem, and the template writes itself.

Related posts

• Decode String - The same push-on-open, pop-on-close stack pattern applied to bracket-encoded repetition
• Valid Parentheses - The foundational stack-based bracket matching problem that introduces push/pop for nesting
• Remove All Adjacent Duplicates in String - Another stack-based string manipulation problem where the stack tracks characters rather than context

CodeBricks breaks the Reverse Substrings problem into its stack context-save and in-place reversal building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the push/reverse/pop flow is automatic. When a nested parentheses problem shows up in your interview, you do not think about it. You just write it.