Reverse Substrings Between Each Pair of Parentheses

summary

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

approach

• This solution uses a stack to keep track of the indices of the characters that need to be reversed
• When a closing parenthesis is encountered, the solution pops the corresponding opening parenthesis index from the stack, reverses the substring between these two indices, and then removes the opening parenthesis from the stack.

complexity

• O(N)

explain

• The solution iterates over the string s
• When it encounters an opening parenthesis, it pushes the current length of the string onto the stack
• When it encounters a closing parenthesis, it pops the corresponding opening parenthesis index from the stack, reverses the substring between these two indices, and then removes the opening parenthesis from the stack
• The solution continues this process until it has processed the entire string.

Solution Code:

class Solution {
public:
    
    string reverseParentheses(string s) {
        string res = "";
        int mystack[2001];
        int stackIdx = 0;
        int N = s.length();
        int idx = 0;
        for(int i = 0 ; i < N; i++){
            if (s[i] == '('){
                mystack[stackIdx++] = res.length();
            } else if (s[i] == ')'){
                int popIdx = mystack[--stackIdx];
                reverse(res.begin()+popIdx, res.end());
            } else {
                res += s[i];
            }
        }
        return res;
    }
};