Watch 10 video solutions for Reverse Substrings Between Each Pair of Parentheses, a medium level problem involving String, Stack. This walkthrough by NeetCodeIO has 11,951 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 2000s only contains lower case English characters and parentheses.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 | 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. |