#1190

Medium

auto_awesomeStack-based state management

LeetCode Problem Workspace

Reverse Substrings Between Each Pair of Parentheses

Reverse all substrings within matched parentheses using a stack-based approach for efficient state tracking and reversal operations.

string stack

Problem Statement

Given a string s containing lowercase English letters and parentheses, reverse the substrings inside every pair of matching parentheses starting from the innermost pair. Remove all parentheses in the final output.

Implement a function that processes nested reversals correctly. The string is guaranteed to have balanced parentheses, and the result must only contain letters in the correct reversed order.

Examples

Example 1

Input: s = "(abcd)"

Output: "dcba"

Example details omitted.

Example 2

Input: s = "(u(love)i)"

Output: "iloveu"

The substring "love" is reversed first, then the whole string is reversed.

Example 3

Input: s = "(ed(et(oc))el)"

Output: "leetcode"

First, we reverse the substring "oc", then "etco", and finally, the whole string.

Constraints

1 <= s.length <= 2000
s only contains lower case English characters and parentheses.
It is guaranteed that all parentheses are balanced.

Solution Approach

Use a Stack to Track Substrings

Iterate through the string character by character, pushing letters onto a stack. When an opening parenthesis is found, push a marker to indicate a new nested level. Upon encountering a closing parenthesis, pop characters until the marker, reverse them, and push the reversed substring back onto the stack.

Handle Nested Reversals Correctly

Since parentheses can be nested, the stack naturally maintains the correct order of substrings at each level. Reversing substrings as soon as a closing parenthesis is found ensures that deeper levels are processed before outer ones, avoiding incorrect concatenation.

Construct Final Result

After processing the entire string, the stack contains segments of the final string in order. Concatenate all stack elements to produce the resulting string without any parentheses, which is the correct fully reversed output.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because each character is pushed and popped at most once. Space complexity is O(n) due to the stack storing all characters and intermediate substrings for nested parentheses.

What Interviewers Usually Probe

Ask about handling nested parentheses and reversing inner substrings first.
Check understanding of stack-based state management for string transformations.
Expect explanation of why reversing at the closing parenthesis ensures correct output.

Common Pitfalls or Variants

Common pitfalls

Failing to reverse only the substring within the current pair of parentheses.
Ignoring nested parentheses and reversing the string globally too early.
Not removing the parentheses from the final output, resulting in incorrect formatting.

Follow-up variants

Instead of reversing, rotate characters within each parentheses segment.
Use a queue instead of a stack to explore alternative traversal strategies.
Handle additional characters like digits or punctuation while reversing substrings.

FAQ

What is the main pattern used in Reverse Substrings Between Each Pair of Parentheses?

The problem relies on stack-based state management to track characters inside nested parentheses and reverse them efficiently.

Can this approach handle multiple nested parentheses?

Yes, using a stack ensures that innermost parentheses are reversed first, maintaining the correct order for all nested levels.

Do we need to remove the parentheses in the output?

Yes, after reversing substrings, all parentheses should be removed to produce the final string containing only letters.

What is the time complexity of this solution?

The solution runs in O(n) time since each character is pushed and popped from the stack at most once.

What common mistakes should I avoid in this problem?

Avoid reversing the entire string at once, mishandling nested parentheses, or leaving parentheses in the final output.

terminal

Solution

Solution 1: Simulation

We can directly use a stack to simulate the reversal process.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def reverseParentheses(self, s: str) -> str:
        stk = []
        for c in s:
            if c == ")":
                t = []
                while stk[-1] != "(":
                    t.append(stk.pop())
                stk.pop()
                stk.extend(t)
            else:
                stk.append(c)
        return "".join(stk)

Solution 2: Brain Teaser

We observe that, when traversing the string, each time we encounter `(` or `)`, we jump to the corresponding `)` or `(` and then reverse the direction of traversal to continue.

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def reverseParentheses(self, s: str) -> str:
        stk = []
        for c in s:
            if c == ")":
                t = []
                while stk[-1] != "(":
                    t.append(stk.pop())
                stk.pop()
                stk.extend(t)
            else:
                stk.append(c)
        return "".join(stk)

Continue Practicing

#1209 remove all adjacent duplicates in string ii #1249 minimum remove to make valid parentheses #1111 maximum nesting depth of two valid parentheses strings