Reverse Substrings Between Each Pair of Parentheses — Editorial

Opening the reading…

Intuitionwhy each closing parenthesis completes exactly one layer

At any point, the letters being collected belong to the innermost currently open pair, or to the part of the string outside all open pairs. When an opening parenthesis appears, the text collected so far belongs outside the new pair, so you save it and start an empty inner substring. This separates the outer context from the content that must be reversed.

A closing parenthesis tells you that the current substring is complete. Reverse it immediately, then place it after the saved outer context. The stack restores the most recently saved context first, so nested pairs are handled from the inside out without needing to find matching positions beforehand. Parentheses themselves are never added to the result.

One closing parenthesis pops one saved context and finishes one reversal.

Approach

Create a stack of strings and an empty current string, because the current string represents the deepest unfinished parenthesized part while the stack preserves every outer context.

When you read an opening parenthesis, push the current string and clear it, because letters before this parenthesis belong outside the new inner substring and must not be reversed with it.

When you read a lowercase letter, append it to the current string, because it belongs to the innermost pair that is currently open, or directly to the final answer when no pair is open.

When you read a closing parenthesis, reverse the current string, because this substring is exactly the content enclosed by the pair that has just ended.

After reversing, prepend the string at the top of the stack and pop that entry, because the saved text came before the opening parenthesis and must remain before the reversed inner text.

Return the current string after the scan, because every balanced closing parenthesis has already removed its parentheses and merged its reversed content into the surrounding context.

Complexitythe stack uses linear space, but repeated nested copying can be quadratic

MEASURE	BOUND	WHY
Time	O(n^2) worst case	The scan visits each input character once, but reversing and concatenating a current substring can touch many letters. In deeply nested input, the same letters are copied or reversed once at each enclosing level, so the total work can reach the sum of O(n) costs over O(n) levels.
Space	O(n) extra space	The stack and current string together hold only text from the input, so their total stored characters are O(n); the returned string is required output and is excluded. The bound remains O(n) in the worst shape, such as deeply nested parentheses or a long saved outer context.

Here n is the length of the input string, including lowercase letters and parentheses.

Annotated solutionC++ · stack of strings · one scan with inside-out merging

CPPScan the string, reverse each completed inner substring, and merge it with the saved outer text.

#include <algorithm>
#include <stack>
#include <string>

using namespace std;

class Solution {
public:
    string reverseParentheses(string s) {
        stack<string> st;
        string cur;

        for (char c : s) {
            if (c == '(') {
                st.push(cur);
                cur.clear();
            } else if (c == ')') {
                reverse(cur.begin(), cur.end());
                cur = st.top() + cur;
                st.pop();
            } else {
                cur += c;
            }
        }

        return cur;
    }
};

The two lines inside the closing-parenthesis branch must happen in this order. Reversing cur completes the innermost pair, while st.top() supplies the text that preceded its opening parenthesis. Prepending that saved text restores the original left-to-right placement before the reversed part; the resulting cur is then ready to be processed as part of an outer pair.