Reverse Substrings Between Each Pair of Parentheses Solution
Reverse Substrings Between Each Pair of Parentheses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Reverse Substrings Between Each Pair of Parentheses is a medium coding problem on strings and stack, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Strings, Stack
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s of lowercase letters and balanced parentheses.
Reverse the substrings inside each pair of matching parentheses, starting from the innermost pair, and return the result with all brackets removed.
Example 1
Input: s = "(abcd)"
Output: dcba
Example 2
Input: s = "(u(love)i)"
Output: iloveu
Explanation: "love" is reversed first, then the whole thing.
Example 3
Input: s = "(ed(et(oc))el)"
Output: leetcode
Constraints
1 <= s.length <= 40s consists of lowercase English letters and balanced parentheses.
Hints for Reverse Substrings Between Each Pair of Parentheses
Hint 1
Keep a stack of character buffers, one per open bracket level.
Hint 2
(starts a new buffer;)reverses the top buffer and appends it to the one below.Hint 3
Everything else is appended to the current buffer, so the innermost pairs resolve first automatically.
How to solve Reverse Substrings Between Each Pair of Parentheses
Keep a stack of character buffers, one per bracket level; ( opens a new buffer, ) reverses the top buffer and appends it to the one below.
Approach
- Start with one empty buffer.
- On
(, push a new buffer; on), pop, reverse, and extend the new top; otherwise append the letter. - Join the base buffer.
Why it works
Innermost pairs close first, so their contents are reversed before being reversed again by an enclosing pair — exactly the specified semantics.
Complexity
- Time —
O(n²) worst case, O(n) typical - Space —
O(n)
Pitfalls
- The linear trick precomputes matching brackets and walks the string flipping direction at each bracket.
Reference solution
Python
def reverseParentheses(s: str) -> str:
stack = [[]]
for ch in s:
if ch == "(":
stack.append([])
elif ch == ")":
inner = stack.pop()
inner.reverse()
stack[-1].extend(inner)
else:
stack[-1].append(ch)
return "".join(stack[0])Java
public static String reverseParentheses(String s) {
StringBuilder out = new StringBuilder();
Deque<Integer> starts = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(') {
starts.push(out.length());
} else if (c == ')') {
int st = starts.pop();
int a = st, b = out.length() - 1;
while (a < b) {
char t = out.charAt(a);
out.setCharAt(a, out.charAt(b));
out.setCharAt(b, t);
a++;
b--;
}
} else {
out.append(c);
}
}
return out.toString();
}C++
string reverseParentheses(string s) {
string out;
vector<int> starts;
for (char c : s) {
if (c == '(') {
starts.push_back((int) out.size());
} else if (c == ')') {
int st = starts.back();
starts.pop_back();
reverse(out.begin() + st, out.end());
} else {
out.push_back(c);
}
}
return out;
}JavaScript
var reverseParentheses = function(s) {
const stack = [[]];
for (let i = 0; i < s.length; i++) {
const c = s.charAt(i);
if (c === "(") {
stack.push([]);
} else if (c === ")") {
const inner = stack.pop();
inner.reverse();
const top = stack[stack.length - 1];
for (let j = 0; j < inner.length; j++) top.push(inner[j]);
} else {
stack[stack.length - 1].push(c);
}
}
return stack[0].join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Stack Data Structure