1190. Reverse Substrings Between Each Pair of Parentheses

Hint

class Solution {
public:
    string reverseParentheses(string s)
    {
        // Stack to keep track of the positions of '('

        // Result string to build the final output

        // Iterate through each character in the input string
        for ()
        {
            if ()
            {
                // When encountering '(', push the current size of res onto the stack
                // This marks the position to start reversing later

            }
            else if ()
            {
                // When encountering ')', get the position of the matching '('

                // Reverse the substring within the parentheses

            }
            else
            {
                // For any other character, append it to the result string

            }
        }
        // Return the final modified string

    }
};

• Brute Force

class Solution {
public:
    string reverseParentheses(string s)
    {
        stack<int> stk;
        string res;

        for (char c : s)
        {
            if (c == '(')
            {
                stk.push(res.size());
            }
            else if (c == ')')
            {
                int start = stk.top(); stk.pop();
                reverse(res.begin() + start, res.end());
            }
            else
            {
                res += c;
            }
        }
        return res;
    }
};

• T: $O(n^2)$
• S: $O(n)$