Introduction

LeetCode 1190 – Reverse Substrings Between Each Pair of Parentheses is a string manipulation problem that requires reversing the substring inside every matching pair of parentheses.

The important part is that reversals must happen from the innermost parentheses outward.

For example:

The substring love is reversed first:

Then the complete content inside the outer parentheses is reversed, producing:

The final answer should contain only the letters. All parentheses must be removed.

A stack is useful here because it allows the opening parenthesis of the current substring to be tracked until its matching closing parenthesis is encountered.

Problem

Question Link-: Reverse Substrings Between Each Pair of Parentheses

Given a string s containing lowercase English letters and parentheses, reverse the strings inside each pair of matching parentheses, starting from the innermost pair.

Return the resulting string without any parentheses.

Example

Another example:

Approach

The key observation is that when a closing parenthesis ) is encountered, the substring belonging to the most recently opened parenthesis needs to be reversed first.

This naturally matches the behavior of a stack.

Step 1: Store opening parentheses

Whenever ( is encountered, its index is pushed onto the stack.

For example:

When reaching nested opening parentheses, the stack stores their positions.

The most recently added opening parenthesis belongs to the innermost substring.

Step 2: Process a closing parenthesis

When ) is encountered:

1. Get the index of the matching ( from the top of the stack.
2. Reverse the characters between those two parentheses.
3. Remove the opening parenthesis index from the stack.

For example:

When ) is reached, oc is reversed:

The same process then happens for the next outer pair.

Step 3: Remove the parentheses

After all reversals are complete, the character array still contains ( and ).

The final traversal simply collects all characters except the parentheses.

Java Solution

The following solution uses a Stack<Integer> to keep track of opening-parenthesis positions and a character array so that the reversals can be performed directly on the string representation.

How the Code Works

rev() method

The rev() method receives:

1. s → character array
2. en → ending index
3. st → starting index

It first builds the reversed substring:

Then the reversed characters are copied back into the original character array:

This changes the substring directly inside the character array.

Stack processing

The main method scans the string from left to right.

When an opening parenthesis is found:

Its index is stored in the stack.

When a closing parenthesis is found:

The top of the stack gives the matching opening parenthesis.

The substring between them is reversed, and then the opening parenthesis is removed from the stack.

This automatically processes nested parentheses from the inside out.

Dry Run

Consider:

Initial character array:

1. First (

Its index is pushed onto the stack.

2. Second (

The opening parenthesis before love is pushed.

3. First )

The top of the stack is index 2.

The substring between index 3 and 6 is:

Reverse it:

Now the string is effectively:

The inner opening parenthesis is removed from the stack.

4. Final )

The remaining opening parenthesis corresponds to the outer substring.

Its contents are now:

Reverse it:

Finally, the parentheses are removed.

Why a Stack Works

The problem specifically says to process the innermost parentheses first.

A stack follows Last In, First Out (LIFO).

For:

the opening parentheses are encountered in order:

The last opening parenthesis belongs to:

Therefore, it must be processed first.

The stack gives exactly this behavior:

This is why a stack is a natural data structure for this problem.

Complexity Analysis

Let n be the length of the input string.

The stack operations themselves take O(n) time.

However, the actual reversal is performed every time a closing parenthesis is encountered. In the provided implementation, the rev() method also builds a temporary String using repeated concatenation.

Therefore, the worst-case time complexity of this implementation can reach O(n²).

The final construction also uses:

Repeated string concatenation can additionally introduce quadratic behavior in Java.

Time Complexity

Space Complexity

The stack and character array require linear auxiliary space.

A Useful Optimization

The overall idea is correct, but two parts of the implementation can be improved:

and

Since Java String objects are immutable, repeated concatenation can create many intermediate strings.

A StringBuilder is generally more appropriate for repeated character construction.

The core stack-based idea, however, remains the same.

Interview Tip

When a string problem involves nested structures, ask whether the processing order follows the structure of a stack.

For parentheses:

the last opened section is the first one that must be completed.

That is a strong signal for using a stack.

A useful pattern to remember is:

Recognizing this pattern can make similar nested-string and bracket problems much easier to approach.

Conclusion

LeetCode 1190 demonstrates how a simple stack can handle nested string operations efficiently at the algorithmic level.

The main idea is to store the positions of opening parentheses and, whenever a closing parenthesis appears, reverse the substring associated with the most recently opened pair.

The important pattern is:

This approach provides a straightforward way to process nested parentheses from the inside out while keeping the implementation relatively simple in Java.