Reverse Substrings Between Each Pair of Parentheses - Solution & Explanation
Problem Statement
You are given a string s that consists of lower case English letters and brackets.
Reverse the strings in each pair of matching parentheses, starting from the innermost one.
Your result should not contain any brackets.
Example 1:
Input: s = "(abcd)" Output: "dcba"
Example 2:
Input: s = "(u(love)i)" Output: "iloveu" Explanation: The substring "love" is reversed first, then the whole string is reversed.
Example 3:
Input: s = "(ed(et(oc))el)" Output: "leetcode" Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.
Constraints:
1 <= s.length <= 2000sonly contains lower case English characters and parentheses.- It is guaranteed that all parentheses are balanced.
Approach Overview
Problem Overview: Given a string containing lowercase letters and parentheses, reverse the characters inside every matched pair of parentheses starting from the innermost pair. After all reversals, return the final string without any parentheses.
Approach 1: Stack-Based Approach (Time: O(n), Space: O(n))
This method simulates the reversal process using a stack. Iterate through the string character by character. Push characters onto the stack until you encounter a closing parenthesis ). At that point, pop characters from the stack until the matching ( appears, which gives you the substring that needs reversing. The popped sequence is already reversed due to stack order, so push the characters back to the stack without the parentheses. Continue scanning until the end. Finally, join all characters in the stack to build the result. Time complexity is O(n) because each character is pushed and popped at most once, and space complexity is O(n) for the stack storage.
Approach 2: Two-Pass String Build with Parenthesis Mapping (Time: O(n), Space: O(n))
This approach treats parentheses as navigation markers rather than explicitly reversing substrings multiple times. First pass: scan the string and use a stack to record indices of (. When you see ), create a bidirectional mapping between the two indices. Second pass: iterate through the string using a direction pointer. Start moving forward, append characters to the result, and whenever you hit a parenthesis index, jump to its mapped partner and reverse the traversal direction. This effectively simulates nested reversals without repeatedly rebuilding substrings. The algorithm runs in O(n) time since each index is visited at most twice, and it uses O(n) extra space for the mapping and result buffer. This technique relies heavily on efficient string traversal and stack-assisted index pairing.
Recommended for interviews: The stack-based approach is the most intuitive and commonly expected solution. It clearly demonstrates understanding of stack operations and nested structure handling. The two-pass index mapping method is more optimized conceptually and avoids repeated reversals, which interviewers often appreciate for its clean linear traversal and clever control of direction.
Approach 1: Stack-Based Approach
Utilize a stack to handle the nested or paired parentheses efficiently. By pushing characters onto a stack until a closing parenthesis is encountered, then reversing the needed substring, you can leverage the stack's LIFO properties to achieve the desired result.
This C solution uses an array-based stack to reverse substrings between parenthesis pairs. It iterates through the string, storing characters inside a stack until a closing parenthesis requires a substring reversal. The reversed substring is then pushed back onto the stack, achieving the desired sequence without parentheses.
Complexity
Time Complexity: O(n).
Space Complexity: O(n) due to the stack usage for storing characters.
Approach 2: Two-Pass String Build Approach
This approach involves separately building the result string in a single pass using an auxiliary data structure to track position swaps. The use of local in-string reversals enables an efficient and clean traversal building mechanism.
This C solution divides the task into first creating pair indices for easy traversal and reversal through position swapping, enabling an efficient processing path that aligns with the stack-based idea but applied to index transformations and direct character use.
Complexity
Time Complexity: O(n).
Space Complexity: O(n), using additional space for parentheses pair tracking and intermediate char arrays.
Approach 3: Simulation
We can directly use a stack to simulate the reversal process.
The time complexity is O(n^2), and the space complexity is O(n), where n is the length of the string s.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Approach 4: 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.
Therefore, we can use an array d to record the position of the corresponding other bracket for each ( or ), i.e., d[i] represents the position of the other bracket corresponding to the bracket at position i. We can directly use a stack to compute the array d.
Then, we traverse the string from left to right. When encountering ( or ), we jump to the corresponding position according to the array d, then reverse the direction and continue traversing until the entire string is traversed.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the string s.
Code
Python
Java
C++
Go
TypeScript
JavaScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Stack-Based Approach | Time Complexity: O(n). |
| Two-Pass String Build Approach | Time Complexity: O(n). |
| Simulation | — |
| Brain Teaser | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Simulation | O(n) | O(n) | Best general approach. Simple to implement and easy to reason about during interviews. |
| Two-Pass String Build with Index Mapping | O(n) | O(n) | Useful when avoiding repeated substring reversals. Demonstrates deeper understanding of traversal and index mapping. |
Video Solution
Reverse Substrings Between Each Pair of Parentheses - Leetcode 1190 - Python • NeetCodeIO • 12,198 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Reverse Substrings Between Each Pair of Parentheses easy or hard?
Reverse Substrings Between Each Pair of Parentheses Python/Java solution
How to solve Reverse Substrings Between Each Pair of Parentheses in O(n)?
What is the best approach for Reverse Substrings Between Each Pair of Parentheses?
Is Reverse Substrings Between Each Pair of Parentheses asked at Google/Amazon/Meta?
What data structure is used in Reverse Substrings Between Each Pair of Parentheses?
What is the time complexity of Reverse Substrings Between Each Pair of Parentheses?
Ready to solve this problem?
Practice Reverse Substrings Between Each Pair of Parentheses with our built-in code editor and test cases.
Practice on FleetCode