Reverse Substrings Between Each Pair of Parentheses solution and explanation
9 more videos on this problem
Reverse Substrings Between Each Pair of Parentheses - Leetcode 1190 - PythonNeetCodeIO · 24:33 · 12K views
1190. Reverse Substrings Between Each Pair of Parentheses | StacK | Wormhole Teleportation techniqueAryan Mittal · 20:00 · 6K views
1190. Reverse Substrings Between Each Pair of Parentheses | LEETCODE MEDIUM | STACKcode Explainer · 5:38 · 4K views
Reverse Substrings Between Each Pair of Parentheses || Leetcode 1190Code with Newton · 17:29 · 2K views
✅ Reverse Substrings Between Each Pair of Parentheses - LeetCode 1190 - Recursion - O(N) - ExplainedLeet Logics · 10:35 · 1K views
1190 Reverse Substrings Between Each Pair of Parentheses - SwiftSwifty LeetCode · 8:11 · 753 views
Reverse Substrings Between Each Pair of Parentheses || Leetcode 1190 || #codign #leetcode #reverseSrajan Agrawal · 18:21 · 130 views
1190. Reverse Substrings Between Each Pair of Parentheses | Stack | Brute force | Optimal | StringLeet's Code · 14:31 · 128 views
LeetCode 1190 - Reverse Substrings Between Each Pair of ParenthesesAlpha-Code · 15:50 · 82 views
LeetCode 1190: Reverse Substrings Between Each Pair of Parentheses| C++ Solution| 100% AcceptanceCodewithAG · 9:40 · 63 views
The problem
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.
def reverseParentheses(s):
stack = []
for char in s:
if char == ')':
queue = []
while stack and stack[-1] != '(':
queue.append(stack.pop())
stack.pop() # pop '('
stack.extend(queue)
else:
stack.append(char)
return ''.join(stack)
s = '(u(love)i)'
print(reverseParentheses(s))import java.util.Stack;
public class ReverseParentheses {
public String reverseParentheses(String s) {
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c != ')') stack.push(c);
else {
StringBuilder sb = new StringBuilder();
while (stack.peek() != '(') {
sb.append(stack.pop());
}
stack.pop(); // pop '('
for (char rc : sb.toString().toCharArray()) stack.push(rc);
}
}
StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) result.append(stack.pop());
return result.reverse().toString();
}
public static void main(String[] args) {
ReverseParentheses rp = new ReverseParentheses();
System.out.println(rp.reverseParentheses("(u(love)i)"));
}
}#include <iostream>
#include <stack>
using namespace std;
string reverseParentheses(string s) {
stack<char> st;
for (char c : s) {
if (c != ')') st.push(c);
else {
string temp = "";
while (!st.empty() && st.top() != '(') {
temp += st.top();
st.pop();
}
st.pop(); // remove '('
for (char x : temp) st.push(x);
}
}
string result = "";
while (!st.empty()) {
result += st.top();
st.pop();
}
reverse(result.begin(), result.end());
return result;
}
int main() {
string s = "(u(love)i)";
cout << reverseParentheses(s) << endl;
return 0;
}function reverseParentheses(s) {
let stack = [];
for (let char of s) {
if (char === ')') {
let queue = [];
while (stack.length && stack[stack.length - 1] !== '(') {
queue.push(stack.pop());
}
stack.pop(); // pop '('
stack.push(...queue);
} else {
stack.push(char);
}
}
return stack.join('');
}
console.log(reverseParentheses('(u(love)i)'));#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char* reverseParentheses(char* s) {
char stack[2000];
int top = -1;
int n = strlen(s);
for (int i = 0; i < n; i++) {
if (s[i] == ')') {
int start = top;
while (stack[top] != '(') top--;
top--; // pop '('
for (int k = start; k > top; k--)
stack[++top] = stack[k];
} else {
stack[++top] = s[i];
}
}
stack[top + 1] = '\0';
return strdup(stack);
}
int main() {
char s[] = "(u(love)i)";
char* result = reverseParentheses(s);
printf("%s\n", result);
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class ReverseParentheses {
public string ReverseParentheses(string s) {
Stack<char> stack = new Stack<char>();
foreach (char c in s) {
if (c != ')') stack.Push(c);
else {
List<char> temp = new List<char>();
while (stack.Peek() != '(') {
temp.Add(stack.Pop());
}
stack.Pop(); // remove '('
foreach (char x in temp) stack.Push(x);
}
}
char[] result = stack.ToArray();
Array.Reverse(result);
return new string(result);
}
public static void Main(string[] args) {
ReverseParentheses rp = new ReverseParentheses();
Console.WriteLine(rp.ReverseParentheses("(u(love)i)"));
}
}This Python implementation uses a list as a stack to reverse parts of the string contained between parentheses. By popping off characters and utilizing a temporary storage list, it reverses the sequence efficiently and appends it back onto the original processing stack.
Time Complexity: O(n).
Space Complexity: O(n) based on stack storage of 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.
def reverseParentheses(s):
n = len(s)
pair = [0] * n
stack = []
for i, char in enumerate(s):
if char == '(':
stack.append(i)
elif char == ')':
j = stack.pop()
pair[i], pair[j] = j, i
i, d = 0, 1
result = []
while i < n:
if s[i] in '()':
i = pair[i]
d = -d
else:
result.append(s[i])
i += d
return ''.join(result)
s = '(ed(et(oc))el)'
print(reverseParentheses(s))import java.util.*;
public class ReverseParentheses {
public String reverseParentheses(String s) {
Stack<Integer> stack = new Stack<>();
int[] pair = new int[s.length()];
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') stack.push(i);
if (s.charAt(i) == ')') {
int j = stack.pop();
pair[i] = j;
pair[j] = i;
}
}
StringBuilder result = new StringBuilder();
for (int i = 0, dir = 1; i < s.length(); i += dir) {
if (s.charAt(i) == '(' || s.charAt(i) == ')') {
i = pair[i];
dir = -dir;
} else {
result.append(s.charAt(i));
}
}
return result.toString();
}
public static void main(String[] args) {
ReverseParentheses rp = new ReverseParentheses();
System.out.println(rp.reverseParentheses("(ed(et(oc))el)"));
}
}#include <iostream>
#include <vector>
#include <stack>
using namespace std;
string reverseParentheses(string s) {
int n = s.length();
vector<int> pair(n, 0);
stack<int> st;
for (int i = 0; i < n; i++) {
if (s[i] == '(') st.push(i);
else if (s[i] == ')') {
int j = st.top(); st.pop();
pair[i] = j;
pair[j] = i;
}
}
string result;
for (int i = 0, d = 1; i < n; i += d) {
if (s[i] == '(' || s[i] == ')') {
i = pair[i];
d = -d;
} else {
result += s[i];
}
}
return result;
}
int main() {
string s = "(ed(et(oc))el)";
cout << reverseParentheses(s) << endl;
return 0;
}function reverseParentheses(s) {
const pair = {};
const stack = [];
for (let i = 0; i < s.length; i++) {
if (s[i] === '(') stack.push(i);
else if (s[i] === ')') {
const j = stack.pop();
pair[i] = j;
pair[j] = i;
}
}
let result = '';
for (let i = 0, dir = 1; i < s.length; i += dir) {
if (s[i] === '(' || s[i] === ')') {
i = pair[i];
dir = -dir;
} else {
result += s[i];
}
}
return result;
}
console.log(reverseParentheses('(ed(et(oc))el)'));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void reverse(char *s, int start, int end) {
while (start < end) {
char temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
}
char* reverseParentheses(char* s) {
int len = strlen(s);
int *pair = malloc(len * sizeof(int));
int *stack = malloc(len * sizeof(int));
int top = -1;
for (int i = 0; i < len; i++) {
if (s[i] == '(') {
stack[++top] = i;
} else if (s[i] == ')') {
int j = stack[top--];
pair[i] = j;
pair[j] = i;
}
}
char *result = malloc(len + 1);
int idx = 0, dir = 1;
for (int i = 0; i < len; i += dir) {
if (s[i] == '(' || s[i] == ')') {
i = pair[i];
dir = -dir;
} else {
result[idx++] = s[i];
}
}
result[idx] = '\0';
free(pair);
free(stack);
return result;
}
int main() {
char s[] = "(ed(et(oc))el)";
char* result = reverseParentheses(s);
printf("%s\n", result);
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class ReverseParentheses {
public string ReverseParentheses(string s) {
Stack<int> stack = new Stack<int>();
int[] pair = new int[s.Length];
for (int i = 0; i < s.Length; i++) {
if (s[i] == '(') stack.Push(i);
else if (s[i] == ')') {
int j = stack.Pop();
pair[i] = j;
pair[j] = i;
}
}
char[] result = new char[s.Length];
int idx = 0, dir = 1;
for (int i = 0; i < s.Length; i += dir) {
if (s[i] == '(' || s[i] == ')') {
i = pair[i];
dir = -dir;
} else {
result[idx++] = s[i];
}
}
return new string(result, 0, idx);
}
public static void Main(string[] args) {
ReverseParentheses rp = new ReverseParentheses();
Console.WriteLine(rp.ReverseParentheses("(ed(et(oc))el)"));
}
}The Python variant applies indexed pair storage to identify parentheses boundaries for the two-pass construction. It offers a clean mechanism to trace and modify the sequence of characters accordingly, ensuring an efficient parsing and building process.
Time Complexity: O(n).
Space Complexity: O(n), additional space for pairing list.
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.
function reverseParentheses(s: string): string {
const stk: string[] = [];
for (const c of s) {
if (c === ')') {
const t: string[] = [];
while (stk.at(-1)! !== '(') {
t.push(stk.pop()!);
}
stk.pop();
stk.push(...t);
} else {
stk.push(c);
}
}
return stk.join('');
}func reverseParentheses(s string) string {
stk := []byte{}
for i := range s {
if s[i] == ')' {
t := []byte{}
for stk[len(stk)-1] != '(' {
t = append(t, stk[len(stk)-1])
stk = stk[:len(stk)-1]
}
stk = stk[:len(stk)-1]
stk = append(stk, t...)
} else {
stk = append(stk, s[i])
}
}
return string(stk)
}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.
function reverseParentheses(s: string): string {
const n = s.length;
const d: number[] = Array(n).fill(0);
const stk: number[] = [];
for (let i = 0; i < n; ++i) {
if (s[i] === '(') {
stk.push(i);
} else if (s[i] === ')') {
const j = stk.pop()!;
d[i] = j;
d[j] = i;
}
}
let i = 0;
let x = 1;
const ans: string[] = [];
while (i < n) {
const c = s.charAt(i);
if ('()'.includes(c)) {
i = d[i];
x = -x;
} else {
ans.push(c);
}
i += x;
}
return ans.join('');
}func reverseParentheses(s string) string {
n := len(s)
d := make([]int, n)
stk := []int{}
for i, c := range s {
if c == '(' {
stk = append(stk, i)
} else if c == ')' {
j := stk[len(stk)-1]
stk = stk[:len(stk)-1]
d[i], d[j] = j, i
}
}
ans := []byte{}
i, x := 0, 1
for i < n {
if s[i] == '(' || s[i] == ')' {
i = d[i]
x = -x
} else {
ans = append(ans, s[i])
}
i += x
}
return string(ans)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Stack-Based Approach | Time Complexity: O(n). |
| Two-Pass String Build Approach | Time Complexity: O(n). |
| Simulation | – |
| Brain Teaser | – |
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. |
Frequently asked questions
Is Reverse Substrings Between Each Pair of Parentheses easy or hard?
The problem is classified as Medium on LeetCode. The main challenge comes from correctly handling nested parentheses and ensuring substrings are reversed in the correct order while maintaining linear time complexity.
Reverse Substrings Between Each Pair of Parentheses Python/Java solution
Python and Java solutions typically implement the stack approach. Iterate through the string, push characters to a stack, and when ')' appears, pop characters until '(' is found, reverse the substring, and push it back. The final stack contents form the resulting string without parentheses.
How to solve Reverse Substrings Between Each Pair of Parentheses in O(n)?
Use either a stack simulation or a two-pass traversal with parenthesis index mapping. The stack method reverses substrings when encountering ')', while the two-pass method builds a mapping of matching parentheses and changes traversal direction during iteration. Both guarantee linear time processing.
What is the best approach for Reverse Substrings Between Each Pair of Parentheses?
The stack-based approach is the most practical solution. Traverse the string, push characters to a stack, and when encountering a closing parenthesis, pop characters until the matching opening parenthesis appears and push the reversed substring back. This runs in O(n) time and O(n) space and cleanly handles nested parentheses.
Is Reverse Substrings Between Each Pair of Parentheses asked at Google/Amazon/Meta?
This problem pattern appears in interviews at companies like Amazon, Google, and Meta because it tests stack usage, nested structure handling, and string manipulation. Variations involving bracket matching or nested reversal logic are common interview questions.
What data structure is used in Reverse Substrings Between Each Pair of Parentheses?
A stack is the primary data structure used to track characters or indices of opening parentheses. It helps process nested structures in a last-in-first-out order, which naturally matches how inner parentheses must be reversed before outer ones.
What is the time complexity of Reverse Substrings Between Each Pair of Parentheses?
The optimal solutions run in O(n) time where n is the length of the string. Each character is processed a constant number of times either through stack push/pop operations or through indexed traversal with parenthesis mapping. Space complexity is O(n) for storing intermediate characters or index mappings.