LeetCode 1190 - Reverse Substrings Between Each Pair of Parentheses

LeetCode Problem 1190

Difficulty: 🟡 Medium
Topics: String, Stack

Solution

Problem Understanding

The problem gives us a string s containing lowercase English letters and balanced parentheses. Our task is to repeatedly reverse the substrings enclosed inside every matching pair of parentheses, starting from the innermost pair first. After all reversals are complete, we must return the final string without any parentheses.

The important detail is that nested parentheses matter. When one pair of parentheses exists inside another pair, the inner substring must be reversed before the outer substring is processed. This means the transformations happen from the deepest nesting level outward.

For example, consider:

(u(love)i)

The innermost substring is:

(love)

Reversing it gives:

(u(evol)i)

Now the outer parentheses contain:

uevoli

Reversing that gives:

iloveu

The final answer removes all parentheses.

The input size is at most 2000 characters. This is small enough that even some quadratic solutions can pass, but repeated substring reconstruction can still become inefficient and messy. Since the parentheses are guaranteed to be balanced, we never need to worry about invalid expressions or unmatched brackets.

Several edge cases are important:

• Strings with no parentheses at all, such as "abc", should simply return "abc".
• Deeply nested parentheses can expose inefficient reversal strategies.
• Empty parentheses such as "()" produce an empty substring and should not break the logic.
• Multiple adjacent parenthesized sections must each be processed independently.
• Nested reversals can restore original ordering in surprising ways, so careful processing order is necessary.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly locate the innermost pair of parentheses, reverse the substring inside it, replace the entire parenthesized portion with the reversed substring, and continue until no parentheses remain.

One way to implement this is:

1. Scan the string from left to right.
2. Whenever a closing parenthesis ) is found, search backward for its matching opening parenthesis (.
3. Extract the substring inside.
4. Reverse it.
5. Rebuild the string without the parentheses.
6. Restart scanning.

This works because reversing the innermost substring first matches the problem requirement. However, every replacement creates a new string, and repeated scans across the string become expensive.

In the worst case, each reversal operation touches nearly the entire string, and there may be many nested pairs. This leads to quadratic time complexity.

Optimal Approach

The key insight is that parentheses define directional changes in traversal.

Instead of repeatedly reconstructing substrings, we can preprocess the matching parentheses positions using a stack. Once we know which parentheses match each other, we can simulate traversal through the string.

The clever trick is:

• Normally, we move left to right.
• When we encounter a parenthesis, we jump to its matching parenthesis and reverse traversal direction.
• Because direction changes naturally simulate substring reversal, we never explicitly reverse substrings.

This produces an elegant linear time solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeated substring rebuilding and rescanning
Optimal	O(n)	O(n)	Uses matching parenthesis indices and directional traversal

Algorithm Walkthrough

Step 1: Match Parentheses Using a Stack

We first preprocess the string to determine which parentheses belong together.

We use a stack to store indices of opening parentheses.

As we scan the string:

• If we see '(', we push its index onto the stack.
• If we see ')', we pop the most recent opening index.
• These two indices form a matching pair.

We store the mapping in a dictionary or array:

partner[left_index] = right_index
partner[right_index] = left_index

This allows constant time jumps between matching parentheses.

Step 2: Traverse the String

We now simulate movement through the string.

We maintain:

• index, the current position
• direction, either 1 for left-to-right or -1 for right-to-left

Initially:

index = 0
direction = 1

Step 3: Process Each Character

While the index stays within bounds:

• If the current character is a letter:

• Append it to the result.

• Move to the next position using the current direction.

• If the current character is a parenthesis:

• Jump to its matching parenthesis using the mapping.

• Reverse the traversal direction.

• Move one step further in the new direction.

The direction reversal is the crucial idea. It naturally simulates substring reversal without explicitly reversing any substring.

Step 4: Build the Final Result

Because parentheses are never appended to the result, the final string automatically excludes them.

We join all collected characters and return the final string.

Why it works

Whenever traversal enters a parenthesized section, direction flips. This means characters inside that section are visited in reverse order. If another nested parenthesis is encountered, direction flips again, restoring the original direction inside the nested section. These alternating direction changes exactly reproduce the required innermost-first reversal behavior.

Since every character is visited at most once during traversal, the algorithm produces the correct reversed output efficiently.

Python Solution

class Solution:
    def reverseParentheses(self, s: str) -> str:
        n = len(s)

        pair = {}
        stack = []

        # Match parentheses
        for index, char in enumerate(s):
            if char == '(':
                stack.append(index)
            elif char == ')':
                opening_index = stack.pop()

                pair[opening_index] = index
                pair[index] = opening_index

        result = []

        index = 0
        direction = 1

        while 0 <= index < n:
            if s[index] == '(' or s[index] == ')':
                index = pair[index]
                direction *= -1
            else:
                result.append(s[index])

            index += direction

        return ''.join(result)

The implementation begins by preprocessing the parentheses relationships. The stack stores indices of opening parentheses. Whenever a closing parenthesis is encountered, we pop the matching opening index and record the relationship in both directions.

The second phase performs directional traversal.

The index variable tracks our current position, while direction determines whether we move left-to-right or right-to-left.

When we encounter a normal character, we append it directly to the result.

When we encounter a parenthesis, we jump to its matching partner and reverse the traversal direction. This effectively simulates reversing the enclosed substring without actually creating reversed substrings.

Finally, we join the collected characters into the final answer.

Go Solution

func reverseParentheses(s string) string {
	n := len(s)

	pair := make(map[int]int)
	stack := []int{}

	// Match parentheses
	for i, ch := range s {
		if ch == '(' {
			stack = append(stack, i)
		} else if ch == ')' {
			openingIndex := stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			pair[openingIndex] = i
			pair[i] = openingIndex
		}
	}

	result := []byte{}

	index := 0
	direction := 1

	for index >= 0 && index < n {
		if s[index] == '(' || s[index] == ')' {
			index = pair[index]
			direction *= -1
		} else {
			result = append(result, s[index])
		}

		index += direction
	}

	return string(result)
}

The Go implementation follows the same logic as the Python solution.

A map[int]int stores matching parenthesis indices, while a slice is used as the stack.

The result is accumulated using a []byte, which is efficient for string construction in Go. Since the input only contains ASCII lowercase letters and parentheses, byte-based processing is completely safe.

Unlike Python lists, Go slices require manual removal of the top stack element using slicing syntax:

stack = stack[:len(stack)-1]

No special handling for integer overflow is required because indices remain within the string length constraints.

Worked Examples

Example 1

Input:

(abcd)

Parenthesis Mapping

Index	Character	Matching Index
0	(	5
5	)	0

Traversal

Step	Index	Character	Direction	Result
1	0	(	1 → -1	""
2	4	d	-1	"d"
3	3	c	-1	"dc"
4	2	b	-1	"dcb"
5	1	a	-1	"dcba"
6	0	(	-1 → 1	"dcba"

Final answer:

dcba

Example 2

Input:

(u(love)i)

Parenthesis Mapping

Index	Character	Matching Index
0	(	9
2	(	7
7	)	2
9	)	0

Traversal

Step	Index	Character	Direction	Result
1	0	(	1 → -1	""
2	8	i	-1	"i"
3	7	)	-1 → 1	"i"
4	3	l	1	"il"
5	4	o	1	"ilo"
6	5	v	1	"ilov"
7	6	e	1	"ilove"
8	7	)	1 → -1	"ilove"
9	1	u	-1	"iloveu"

Final answer:

iloveu

Example 3

Input:

(ed(et(oc))el)

Parenthesis Mapping

Index	Character	Matching Index
0	(	13
3	(	10
6	(	9
9	)	6
10	)	3
13	)	0

Traversal Result

The traversal sequence produces:

leetcode

The nested direction reversals naturally simulate:

1. "oc" → "co"
2. "etco" → "octe"
3. Entire substring reversal → "leetcode"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed at most once
Space	O(n)	Stack, parenthesis mapping, and output storage

The preprocessing step scans the string once to match parentheses. The traversal phase also visits each position at most once because jumps occur in constant time using the mapping table.

Although direction changes occur frequently, each character contributes only constant work overall, giving linear time complexity.

The extra space comes from:

• The stack used for matching parentheses
• The mapping structure
• The output buffer

All of these scale linearly with the input size.

Test Cases

solution = Solution()

assert solution.reverseParentheses("(abcd)") == "dcba"  # simple reversal

assert solution.reverseParentheses("(u(love)i)") == "iloveu"  # nested reversal

assert solution.reverseParentheses("(ed(et(oc))el)") == "leetcode"  # multiple nesting levels

assert solution.reverseParentheses("abc") == "abc"  # no parentheses

assert solution.reverseParentheses("a(bc)d") == "acbd"  # single middle section

assert solution.reverseParentheses("a(bcdefghijkl(mno)p)q") == "apmnolkjihgfedcbq"  # deep nesting

assert solution.reverseParentheses("()") == ""  # empty parentheses

assert solution.reverseParentheses("(a)") == "a"  # single character inside parentheses

assert solution.reverseParentheses("((abc))") == "abc"  # double reversal restores order

assert solution.reverseParentheses("(ab(cd)ef)") == "fecdba"  # nested inner section

assert solution.reverseParentheses("x(yz)") == "xzy"  # suffix reversal

assert solution.reverseParentheses("(x(y(z)))") == "yzx"  # multiple nested layers

Test Summary

Test	Why
(abcd)	Basic reversal
(u(love)i)	Nested parentheses
(ed(et(oc))el)	Multiple nesting levels
abc	No parentheses
a(bc)d	Parentheses in the middle
a(bcdefghijkl(mno)p)q	Deep nesting stress test
()	Empty substring
(a)	Single character reversal
((abc))	Double reversal behavior
(ab(cd)ef)	Nested mixed sections
x(yz)	Reversal near end of string
(x(y(z)))	Multiple direction flips

Edge Cases

One important edge case is a string with no parentheses at all, such as "abc". A buggy implementation might assume every string contains at least one parenthesized section and fail unnecessarily. In this implementation, traversal simply appends every character directly to the result because no direction changes ever occur.

Another critical case is empty parentheses:

()

Some substring-based approaches accidentally produce index errors or attempt invalid reversals on empty ranges. In this solution, the traversal simply jumps across the matching parentheses and reverses direction without appending any characters, correctly producing an empty string.

Deeply nested parentheses are another common source of bugs. For example:

((abc))

The inner reversal produces "cba", while the outer reversal restores the original order "abc". Implementations that reverse substrings in the wrong order often fail here. The directional traversal method handles nesting naturally because each pair of parentheses flips traversal direction exactly once.

A final tricky case involves adjacent nested sections with characters outside parentheses, such as:

a(bc)d

The algorithm must preserve characters outside parentheses while reversing only the enclosed substring. Since traversal only changes direction inside matched pairs, outer characters remain in their original positions automatically.