Problem Description

You are given a string s that consists of lowercase English letters and brackets (parentheses).

Your task is to reverse the strings within each pair of matching parentheses, starting from the innermost pairs first. After performing all the reversals, the final result should not contain any brackets.

For example:

• If s = "(abcd)", the output would be "dcba" (reverse the content inside the parentheses and remove the brackets)
• If s = "(u(love)i)", you would first reverse "love" to get "evol", then reverse "uevoli" to get "iloveu"
• If s = "(ed(et(oc))el)", you would process from innermost to outermost:
  • First reverse "oc" to get "co"
  • Then reverse "etco" to get "octe"
  • Finally reverse "edocteel" to get "leetcode"

The algorithm uses a stack to handle this process. As we iterate through the string:

• When we encounter a closing parenthesis ), we pop characters from the stack until we reach the matching opening parenthesis (, collecting these characters in reverse order
• We then push these reversed characters back onto the stack
• For any other character (letters or opening parenthesis), we simply push it onto the stack
• At the end, we join all characters in the stack to form the final result

Intuition

The key insight is recognizing that parentheses create a nested structure, and we need to process them from the innermost level outward. This naturally suggests using a stack data structure.

Think about how we manually solve this problem: when we see nested parentheses like "(a(bc)d)", we first identify the innermost pair (bc), reverse it to get cb, then work our way outward. A stack perfectly mimics this behavior because it follows Last-In-First-Out (LIFO) principle.

As we traverse the string character by character, we can push everything onto the stack. The crucial moment comes when we encounter a closing parenthesis ). At this point, we know we've completed reading one pair of parentheses, and everything between the current ) and its matching ( on the stack needs to be reversed.

Here's the clever part: when we pop characters from the stack after seeing ), we're already getting them in reverse order! For example, if the stack contains ['(', 'a', 'b', 'c'] and we encounter ), popping 'c', then 'b', then 'a' gives us the reversed sequence naturally.

After collecting the reversed characters, we discard the opening parenthesis ( and push the reversed characters back onto the stack. This ensures that if there are outer parentheses, these reversed characters will be part of the next reversal operation.

By processing each closing parenthesis this way, we handle all nested levels correctly, and the stack automatically maintains the correct order of characters. At the end, the stack contains only letters in the final order, with all parentheses processed and removed.

Learn more about Stack patterns.

Solution Approach

The solution uses a stack-based simulation approach to process the string character by character.

Algorithm Steps:

1. Initialize an empty stack stk = [] to store characters as we process them.

2. Iterate through each character c in the string s:

   • If c is a closing parenthesis ")":
     • Create a temporary list t = [] to collect characters that need to be reversed
     • Keep popping from the stack while the top element is not an opening parenthesis "(":

       while stk[-1] != "(":
           t.append(stk.pop())

     • Once we reach the "(", pop it from the stack to remove it: stk.pop()
     • Extend the stack with the collected characters in t: stk.extend(t)
     • Note: Since we popped characters from the stack, they're already in reversed order in t
   • Otherwise (for letters and opening parenthesis):
     • Simply push the character onto the stack: stk.append(c)

3. Return the final result by joining all characters remaining in the stack: return "".join(stk)

Why this works:

• When we encounter ), all characters between it and its matching ( are on top of the stack
• Popping these characters naturally reverses their order (LIFO property)
• By pushing the reversed characters back, they become part of any outer parenthesis processing
• The process handles nested parentheses correctly because inner pairs are processed before outer ones
• After processing all parentheses, only letters remain in the stack in the correct order

Time Complexity: O(n) where n is the length of the string, as each character is pushed and popped at most once.

Space Complexity: O(n) for the stack storage.

Example Walkthrough

Let's trace through the example s = "(u(love)i)" step by step to see how the stack-based solution works.

Initial state: stk = [], s = "(u(love)i)"

Step 1: Process '('

• Not a closing parenthesis, so push to stack
• stk = ['(']

Step 2: Process 'u'

• Not a closing parenthesis, so push to stack
• stk = ['(', 'u']

Step 3: Process '('

• Not a closing parenthesis, so push to stack
• stk = ['(', 'u', '(']

Step 4: Process 'l'

• Not a closing parenthesis, so push to stack
• stk = ['(', 'u', '(', 'l']

Step 5: Process 'o'

• Not a closing parenthesis, so push to stack
• stk = ['(', 'u', '(', 'l', 'o']

Step 6: Process 'v'

• Not a closing parenthesis, so push to stack
• stk = ['(', 'u', '(', 'l', 'o', 'v']

Step 7: Process 'e'

• Not a closing parenthesis, so push to stack
• stk = ['(', 'u', '(', 'l', 'o', 'v', 'e']

Step 8: Process ')' (first closing parenthesis)

• This IS a closing parenthesis, so we need to reverse
• Initialize t = []
• Pop from stack while top ≠ '(':
  • Pop 'e', add to t: t = ['e']
  • Pop 'v', add to t: t = ['e', 'v']
  • Pop 'o', add to t: t = ['e', 'v', 'o']
  • Pop 'l', add to t: t = ['e', 'v', 'o', 'l']
  • Top is now '(', stop popping
• Pop the '(' to remove it
• Extend stack with t: stk = ['(', 'u', 'e', 'v', 'o', 'l']
• Note: "love" has been reversed to "evol"!

Step 9: Process 'i'

• Not a closing parenthesis, so push to stack
• stk = ['(', 'u', 'e', 'v', 'o', 'l', 'i']

Step 10: Process ')' (second closing parenthesis)

• This IS a closing parenthesis, so we need to reverse
• Initialize t = []
• Pop from stack while top ≠ '(':
  • Pop 'i', add to t: t = ['i']
  • Pop 'l', add to t: t = ['i', 'l']
  • Pop 'o', add to t: t = ['i', 'l', 'o']
  • Pop 'v', add to t: t = ['i', 'l', 'o', 'v']
  • Pop 'e', add to t: t = ['i', 'l', 'o', 'v', 'e']
  • Pop 'u', add to t: t = ['i', 'l', 'o', 'v', 'e', 'u']
  • Top is now '(', stop popping
• Pop the '(' to remove it
• Extend stack with t: stk = ['i', 'l', 'o', 'v', 'e', 'u']

Final step: Join the stack

• "".join(stk) = "iloveu"

The algorithm correctly processes the innermost parentheses first (reversing "love" to "evol"), then processes the outer parentheses (reversing "uevoli" to "iloveu"), giving us the expected result.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm iterates through each character in the string once using the outer loop, which takes O(n) time. However, when encountering a closing parenthesis ")", the inner while loop pops elements from the stack until it finds the matching opening parenthesis "(". In the worst case, this operation can pop up to O(n) elements. After popping these elements into temporary array t, the stk.extend(t) operation adds them back to the stack, which also takes O(n) time in the worst case.

Consider a nested parentheses pattern like "(((...)))". Each closing parenthesis triggers operations that can potentially process a significant portion of the characters already in the stack. Since there can be up to n/2 closing parentheses and each can trigger O(n) operations, the overall time complexity is O(n²).

Space Complexity: O(n)

The algorithm uses two main data structures:

• Stack stk: In the worst case, it can store all n characters from the input string
• Temporary array t: In the worst case, it can store up to n characters when reversing content between parentheses

Since these structures are not used simultaneously at their maximum capacity (when t is filled, elements are popped from stk), and the total number of characters stored never exceeds the input size, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrectly Reversing the Characters

The Issue: A common mistake is to reverse the temp_chars list before extending the stack, thinking that we need to explicitly reverse the collected characters:

# INCORRECT approach
while stack[-1] != "(":
    temp_chars.append(stack.pop())
stack.pop()
stack.extend(reversed(temp_chars))  # Wrong! Double reversal

Why This Fails: When we pop characters from the stack into temp_chars, they're already in reversed order due to the LIFO (Last In, First Out) nature of the stack. Adding another reversal would cancel out the intended reversal effect.

Example: For "(abc)":

• Stack before ): ['(', 'a', 'b', 'c']
• After popping into temp_chars: ['c', 'b', 'a'] (already reversed!)
• If we reverse again: ['a', 'b', 'c'] (back to original order - wrong!)

Correct Solution: Simply extend the stack with temp_chars as-is:

stack.extend(temp_chars)  # Correct - already in reversed order

Pitfall 2: Not Handling Empty Parentheses

The Issue: The code might crash when encountering empty parentheses "()" if not careful with stack access:

# Potential issue if not checking stack bounds
while stack[-1] != "(":  # Could crash if stack is empty
    temp_chars.append(stack.pop())

Why This Fails: While the problem likely guarantees valid input, in production code, accessing stack[-1] on an empty stack would raise an IndexError.

Correct Solution: Add a safety check or ensure the logic handles empty content gracefully:

while stack and stack[-1] != "(":
    temp_chars.append(stack.pop())

The current solution actually handles empty parentheses correctly since:

• When we encounter ) after (, the while loop condition immediately fails
• We pop the ( and extend with an empty temp_chars list
• Result: Empty parentheses are simply removed

Pitfall 3: Using String Concatenation Instead of List

The Issue: Building the result using string concatenation instead of a list:

# INEFFICIENT approach
stack = ""
for char in s:
    if char == ")":
        temp = ""
        i = len(stack) - 1
        while stack[i] != "(":
            temp += stack[i]
            i -= 1
        stack = stack[:i] + temp
    else:
        stack += char

Why This Fails:

• String concatenation in Python creates new string objects each time (strings are immutable)
• This leads to O(n²) time complexity instead of O(n)
• String manipulation becomes complex and error-prone

Correct Solution: Use a list-based stack as shown in the original solution, which provides O(1) append and pop operations.