# Reverse Substrings Between Each Pair of Parentheses
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses)
Canonical: https://scaleengineer.com/dsa/problems/reverse-substrings-between-each-pair-of-parentheses
**Data structures:** String, Stack
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda)
---
## 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 <= 2000`
* `s` only contains lower case English characters and parentheses.
* It is guaranteed that all parentheses are balanced.

# Approaches
## Brute Force with Repeated Search and Replace
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.
**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.
**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.
### Explanation
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.
```java
class Solution {
    public String reverseParentheses(String s) {
        int openParenIndex = s.lastIndexOf('(');
        while (openParenIndex != -1) {
            int closeParenIndex = s.indexOf(')', openParenIndex);
            
            String reversed = new StringBuilder(s.substring(openParenIndex + 1, closeParenIndex)).reverse().toString();
            
            s = s.substring(0, openParenIndex) + reversed + s.substring(closeParenIndex + 1);
            
            openParenIndex = s.lastIndexOf('(');
        }
        return s;
    }
}
```
### Algorithm
- 1. Start a loop that continues as long as the string contains `'('`.
- 2. Inside the loop, find the index of the last `'('`. This ensures we work from the inside out.
- 3. Find the index of the first `')'` that appears after this `'('`.
- 4. Extract the substring between these two parentheses.
- 5. Reverse the extracted substring.
- 6. Reconstruct the main string by concatenating the part before the `'('`, the reversed substring, and the part after the `')'`.
- 7. Repeat the loop.
- 8. Once the loop finishes, return the modified string.

## Stack-Based Approach
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.
**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`.
**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.
### Explanation
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.
```java
import java.util.Stack;

class Solution {
    public String reverseParentheses(String s) {
        Stack<StringBuilder> stack = new Stack<>();
        stack.push(new StringBuilder());

        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(new StringBuilder());
            } else if (c == ')') {
                StringBuilder reversedSegment = stack.pop().reverse();
                stack.peek().append(reversedSegment);
            } else {
                stack.peek().append(c);
            }
        }
        return stack.pop().toString();
    }
}
```
### Algorithm
- 1. Initialize a stack and push an empty `StringBuilder` onto it.
- 2. Iterate through each character `c` of the input string `s`.
- 3. If `c` is an opening parenthesis `'('`, push a new empty `StringBuilder` onto the stack.
- 4. If `c` is a closing parenthesis `')'`, pop the top `StringBuilder`, reverse it, and append its content to the new top `StringBuilder` on the stack.
- 5. If `c` is a letter, append it to the `StringBuilder` currently at the top of the stack.
- 6. After the loop, the final result is the string contained in the single `StringBuilder` left on the stack.

## Optimal O(N) Approach with Pre-computation
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.
**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`.
**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.
### Explanation
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.
```java
import java.util.Stack;

class Solution {
    public String reverseParentheses(String s) {
        int n = s.length();
        int[] pair = new int[n];
        Stack<Integer> openParenIndices = new Stack<>();

        // First pass: find pairs of parentheses
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) == '(') {
                openParenIndices.push(i);
            } else if (s.charAt(i) == ')') {
                int j = openParenIndices.pop();
                pair[i] = j;
                pair[j] = i;
            }
        }

        StringBuilder result = new StringBuilder();
        int currIndex = 0;
        int direction = 1;

        // Second pass: build the result string
        while (currIndex < n) {
            char c = s.charAt(currIndex);
            if (c == '(' || c == ')') {
                currIndex = pair[currIndex]; // Jump to the matching parenthesis
                direction = -direction; // Reverse direction
            } else {
                result.append(c);
            }
            currIndex += direction;
        }

        return result.toString();
    }
}
```
### Algorithm
- 1. Create an integer array `pair` of the same size as the input string `s`.
- 2. 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`.
- 3. Initialize an empty `StringBuilder` `result`, a current index `i = 0`, and a direction `dir = 1`.
- 4. Loop while `i` is within the bounds of the string (`0 <= i < n`).
- 5. If `s[i]` is a letter, append it to `result`.
- 6. If `s[i]` is a parenthesis, jump to its pair by setting `i = pair[i]` and reverse the direction by setting `dir = -dir`.
- 7. In every step of the loop, update the index: `i += dir`.
- 8. Return the final string from `result`.

# Solutions
### Java

```java
class 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 (); } }
```

### JavaScript

```javascript
/** * @param {string} s * @return {string} */ var reverseParentheses =
  function (s) {
    const n = s.length;
    const d = new Array(n).fill(0);
    const stk = [];
    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 = [];
    while (i < n) {
      const c = s.charAt(i);
      if (c == " ( " || c == " ) ") {
        i = d[i];
        x = -x;
      } else {
        ans.push(c);
      }
      i += x;
    }
    return ans.join("");
  };

```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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 )
```