Reverse Substrings Between Each Pair of Parentheses

Med

#1115Time: O(N^3). Let N be the length of the string and K be the number of parenthesis pairs. The `while` loop runs K times. Inside the loop, `lastIndexOf`, `indexOf`, `substring`, and string concatenation can all take up to O(N) time. In the worst case, K is proportional to N, and string operations create new strings, leading to a complexity around `O(K * N^2)`, which can be `O(N^3)`.Space: O(N). In each step of the loop, new strings are created whose total length is proportional to N.1 company

Data structures

String Stack

Companies

Agoda

Prompt

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 <= 2000
s only contains lower case English characters and parentheses.
It is guaranteed that all parentheses are balanced.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach simulates the process directly. It repeatedly finds the innermost pair of parentheses, reverses the content within them, and updates the string. This continues until no parentheses are left.

Algorithm

1. Start a loop that continues as long as the string contains '('.
1. Inside the loop, find the index of the last '('. This ensures we work from the inside out.
1. Find the index of the first ')' that appears after this '('.
1. Extract the substring between these two parentheses.
1. Reverse the extracted substring.
1. Reconstruct the main string by concatenating the part before the '(', the reversed substring, and the part after the ')'.
1. Repeat the loop.
1. Once the loop finishes, return the modified string.

Walkthrough

The algorithm works by iteratively simplifying the string. In a loop, we search for the first occurrence of a closing parenthesis ')'. Once found, we search backward from that position to find the corresponding opening parenthesis '('. This pair is guaranteed to be an innermost one because we picked the first ')'. We then extract the substring between these parentheses. This substring is reversed. The original string segment, including the parentheses (...), is replaced by the newly reversed substring. This process repeats until no more opening parentheses '(' can be found in the string. While simple to conceptualize, this method is highly inefficient due to the overhead of repeated string searching and modifications, as string objects are immutable in Java, leading to the creation of new string objects in each iteration.

1class Solution {2    public String reverseParentheses(String s) {3        int openParenIndex = s.lastIndexOf('(');4        while (openParenIndex != -1) {5            int closeParenIndex = s.indexOf(')', openParenIndex);6            7            String reversed = new StringBuilder(s.substring(openParenIndex + 1, closeParenIndex)).reverse().toString();8            9            s = s.substring(0, openParenIndex) + reversed + s.substring(closeParenIndex + 1);10            11            openParenIndex = s.lastIndexOf('(');12        }13        return s;14    }15}

Complexity

Time

O(N^3). Let N be the length of the string and K be the number of parenthesis pairs. The `while` loop runs K times. Inside the loop, `lastIndexOf`, `indexOf`, `substring`, and string concatenation can all take up to O(N) time. In the worst case, K is proportional to N, and string operations create new strings, leading to a complexity around `O(K * N^2)`, which can be `O(N^3)`.

Space

O(N). In each step of the loop, new strings are created whose total length is proportional to N.

Trade-offs

Pros

Simple to understand and implement.
Directly follows the problem description's logic.

Cons

Extremely inefficient due to repeated string traversals and manipulations.
Not suitable for large inputs as it would likely result in a "Time Limit Exceeded" error.

A more optimized approach uses a stack to handle the nested structure of the parentheses. We iterate through the string, building up substrings at different nesting levels. When a closing parenthesis is encountered, we reverse the most recently built substring and append it to the string of the parent level.

Algorithm

1. Initialize a stack and push an empty StringBuilder onto it.
1. Iterate through each character c of the input string s.
1. If c is an opening parenthesis '(', push a new empty StringBuilder onto the stack.
1. If c is a closing parenthesis ')', pop the top StringBuilder, reverse it, and append its content to the new top StringBuilder on the stack.
1. If c is a letter, append it to the StringBuilder currently at the top of the stack.
1. After the loop, the final result is the string contained in the single StringBuilder left on the stack.

Walkthrough

This method processes the string in a single pass. We use a stack to keep track of the strings being built. A good choice is a stack of StringBuilder objects for efficient string manipulation. We start by pushing an empty StringBuilder onto the stack, which will hold the final result. We iterate through the input string character by character:

If we see a letter, we append it to the StringBuilder at the top of the stack.
If we see an '(', it signifies the start of a new, nested level. We push a new, empty StringBuilder onto the stack.
If we see a ')', it signifies the end of the current level. We pop the StringBuilder from the stack, reverse its content, and then append this reversed string to the StringBuilder that is now at the top of the stack (which corresponds to the parent level). After iterating through the entire string, the stack will contain a single StringBuilder with the final, correctly reversed string.

1import java.util.Stack;2 3class Solution {4    public String reverseParentheses(String s) {5        Stack<StringBuilder> stack = new Stack<>();6        stack.push(new StringBuilder());7 8        for (char c : s.toCharArray()) {9            if (c == '(') {10                stack.push(new StringBuilder());11            } else if (c == ')') {12                StringBuilder reversedSegment = stack.pop().reverse();13                stack.peek().append(reversedSegment);14            } else {15                stack.peek().append(c);16            }17        }18        return stack.pop().toString();19    }20}

Complexity

Time

O(N^2). We iterate through the string once (`O(N)`). However, the reversal operation can be expensive. In a worst-case scenario like `(a(b(c...)))`, the lengths of the strings being reversed are 1, 2, 3, ..., up to `O(N)`. The sum of these lengths is `1 + 2 + ... + N/2`, which is `O(N^2)`. Therefore, the total time complexity is dominated by the reversals.

Space

O(N). The total number of characters stored across all `StringBuilder`s in the stack at any point will not exceed the length of the input string `N`.

Trade-offs

Pros

Much more efficient than the brute-force approach.
Handles the nested structure elegantly.
Uses a single pass over the input string.

Cons

The O(N^2) complexity can still be too slow for certain deeply nested inputs.

This is the most efficient approach. It avoids building intermediate strings and explicit reversals by first pre-computing the matching parenthesis pairs. Then, it traverses the string in a "wormhole" fashion, changing direction at each parenthesis to simulate the reversals, and builds the final string in a single pass.

Algorithm

1. Create an integer array pair of the same size as the input string s.
1. Use a stack to pre-compute the indices of matching parentheses. Iterate through s:
- If s[i] == '(', push i onto the stack.
- If s[i] == ')', pop an index j from the stack. Set pair[i] = j and pair[j] = i.
1. Initialize an empty StringBuilder result, a current index i = 0, and a direction dir = 1.
1. Loop while i is within the bounds of the string (0 <= i < n).
1. If s[i] is a letter, append it to result.
1. If s[i] is a parenthesis, jump to its pair by setting i = pair[i] and reverse the direction by setting dir = -dir.
1. In every step of the loop, update the index: i += dir.
1. Return the final string from result.

Walkthrough

This clever method consists of two main phases: 1. Pre-computation: We first iterate through the string to find and map every opening parenthesis to its corresponding closing parenthesis, and vice-versa. We can use a stack to find the pairs: when we see an '(', push its index onto the stack; when we see a ')', pop an index, and we have found a pair. We store these index pairs in an array, say pair, where pair[i] = j and pair[j] = i. 2. Result Construction: We then build the result string by traversing the original string s. We use a pointer i for the current position and a variable direction (1 for forward, -1 for backward). We start at index 0 with a forward direction.

When the character at i is a letter, we append it to our result.
When the character is a parenthesis ('(' or ')'), we treat it as a "portal". We jump to its matching parenthesis by setting i = pair[i] and then reverse our direction of traversal (direction *= -1).
We then advance our pointer i by direction and repeat until we have traversed all characters. This approach effectively determines the final position of each character without performing any actual string reversals, leading to a linear time complexity.

1import java.util.Stack;2 3class Solution {4    public String reverseParentheses(String s) {5        int n = s.length();6        int[] pair = new int[n];7        Stack<Integer> openParenIndices = new Stack<>();8 9        // First pass: find pairs of parentheses10        for (int i = 0; i < n; ++i) {11            if (s.charAt(i) == '(') {12                openParenIndices.push(i);13            } else if (s.charAt(i) == ')') {14                int j = openParenIndices.pop();15                pair[i] = j;16                pair[j] = i;17            }18        }19 20        StringBuilder result = new StringBuilder();21        int currIndex = 0;22        int direction = 1;23 24        // Second pass: build the result string25        while (currIndex < n) {26            char c = s.charAt(currIndex);27            if (c == '(' || c == ')') {28                currIndex = pair[currIndex]; // Jump to the matching parenthesis29                direction = -direction; // Reverse direction30            } else {31                result.append(c);32            }33            currIndex += direction;34        }35 36        return result.toString();37    }38}

Complexity

Time

O(N). The first pass to find parenthesis pairs takes `O(N)`. The second pass to build the result string also takes `O(N)` because each character is visited exactly once.

Space

O(N). We use an array `pair` of size `N` to store the parenthesis mappings and a `StringBuilder` to build the result, which can also grow up to size `N`.

Trade-offs

Pros

Optimal time complexity.
Very efficient as it avoids costly intermediate string operations.

Cons

The logic is less intuitive than the stack-based approach.
Requires an initial pass and extra space for the pair array.

Solutions

Solution

1class Solution { public String reverseParentheses ( String s ) { int n = s . length (); int [] d = new int [ n ]; Deque < Integer > stk = new ArrayDeque <>(); for ( int i = 0 ; i < n ; ++ i ) { if ( s . charAt ( i ) == '(' ) { stk . push ( i ); } else if ( s . charAt ( i ) == ')' ) { int j = stk . pop (); d [ i ] = j ; d [ j ] = i ; } } StringBuilder ans = new StringBuilder (); int i = 0 , x = 1 ; while ( i < n ) { if ( s . charAt ( i ) == '(' || s . charAt ( i ) == ')' ) { i = d [ i ]; x = - x ; } else { ans . append ( s . charAt ( i )); } i += x ; } return ans . toString (); } }

1/** * @param {string} s * @return {string} */ var reverseParentheses =2  function (s) {3    const n = s.length;4    const d = new Array(n).fill(0);5    const stk = [];6    for (let i = 0; i < n; ++i) {7      if (s[i] == " ( ") {8        stk.push(i);9      } else if (s[i] == " ) ") {10        const j = stk.pop();11        d[i] = j;12        d[j] = i;13      }14    }15    let i = 0;16    let x = 1;17    const ans = [];18    while (i < n) {19      const c = s.charAt(i);20      if (c == " ( " || c == " ) ") {21        i = d[i];22        x = -x;23      } else {24        ans.push(c);25      }26      i += x;27    }28    return ans.join("");29  };

1class Solution { public: string reverseParentheses ( string s ) { string stk ; for ( char & c : s ) { if ( c == ')' ) { string t ; while ( stk . back () != '(' ) { t . push_back ( stk . back ()); stk . pop_back (); } stk . pop_back (); stk += t ; } else { stk . push_back ( c ); } } return stk ; } };

1class Solution : def reverseParentheses ( self , s : str ) -> str : stk = [] for c in s : if c == ')' : t = [] while stk [ - 1 ] != '(' : t . append ( stk . pop ()) stk . pop () stk . extend ( t ) else : stk . append ( c ) return '' . join ( stk )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1class Solution { public String reverseParentheses ( String s ) { int n = s . length (); int [] d = new int [ n ]; Deque < Integer > stk = new ArrayDeque <>(); for ( int i = 0 ; i < n ; ++ i ) { if ( s . charAt ( i ) == '(' ) { stk . push ( i ); } else if ( s . charAt ( i ) == ')' ) { int j = stk . pop (); d [ i ] = j ; d [ j ] = i ; } } StringBuilder ans = new StringBuilder (); int i = 0 , x = 1 ; while ( i < n ) { if ( s . charAt ( i ) == '(' || s . charAt ( i ) == ')' ) { i = d [ i ]; x = - x ; } else { ans . append ( s . charAt ( i )); } i += x ; } return ans . toString (); } }

1/** * @param {string} s * @return {string} */ var reverseParentheses =2  function (s) {3    const n = s.length;4    const d = new Array(n).fill(0);5    const stk = [];6    for (let i = 0; i < n; ++i) {7      if (s[i] == " ( ") {8        stk.push(i);9      } else if (s[i] == " ) ") {10        const j = stk.pop();11        d[i] = j;12        d[j] = i;13      }14    }15    let i = 0;16    let x = 1;17    const ans = [];18    while (i < n) {19      const c = s.charAt(i);20      if (c == " ( " || c == " ) ") {21        i = d[i];22        x = -x;23      } else {24        ans.push(c);25      }26      i += x;27    }28    return ans.join("");29  };

1class Solution { public: string reverseParentheses ( string s ) { string stk ; for ( char & c : s ) { if ( c == ')' ) { string t ; while ( stk . back () != '(' ) { t . push_back ( stk . back ()); stk . pop_back (); } stk . pop_back (); stk += t ; } else { stk . push_back ( c ); } } return stk ; } };

1class Solution : def reverseParentheses ( self , s : str ) -> str : stk = [] for c in s : if c == ')' : t = [] while stk [ - 1 ] != '(' : t . append ( stk . pop ()) stk . pop () stk . extend ( t ) else : stk . append ( c ) return '' . join ( stk )

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.