> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/stack/1190.-reverse-substrings-between-each-pair-of-parentheses.md).

# 1190. Reverse Substrings Between Each Pair of Parentheses

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.
```

**Example 4:**

```
Input: s = "a(bcdefghijkl(mno)p)q"
Output: "apmnolkjihgfedcbq"
```

**Constraints:**

* `0 <= s.length <= 2000`
* `s` only contains lower case English characters and parentheses.
* It's guaranteed that all parentheses are balanced.

```cpp
// Brute Force
string reverseParentheses(string s) { // time: O(n^2); space: O(n)
    stack<int> st; // store each reverse starting postion
    string res;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '(') {
            st.push(res.length());
        } else if (s[i] == ')') {
            int j = st.top(); st.pop();
            reverse(res.begin() + j, res.end());
        } else {
            res += s[i];
        }
    }
    return res;
}
```

```cpp
// O(n) Method
string reverseParentheses(string s) { // time: O(n); space: O(n)
    int n = s.length();
    stack<int> st; 
    vector<int> pair(n); // parentheses pair
    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 res;
    for (int i = 0, d = 1; i < n; i += d) {
        if (s[i] == '(' || s[i] == ')') {
            i = pair[i];
            d = -d;
        } else {
            res += s[i];
        }
    }
    return res;
}
```