Start learning free

LESSON 295 OF 343 · STACK

Reverse Substrings Between Parentheses in C++: A Stack of Strings

Practice O(n^2) Read the full explanation

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 = "(yme(oc(da))gla)"
Output: "algocademy"
Explanation: First, we reverse the substring "da", then "ocad", 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.

STEP 1 OF 9
    Ctrl + Enter to check

    C++ · STACK

    Reverse Substrings Between Each Pair Of Parentheses in C++, explained

    Problem overview

    The function reverseParentheses receives a string s of lowercase letters and balanced parentheses. It must reverse the text inside every pair of matching parentheses, working from the innermost pair outwards, and return the result with no parentheses left.

    For "(abcd)" the answer is "dcba". For "(u(love)i)", love is reversed first, giving (uevoli), and then the whole content is reversed, giving "iloveu". For "(yme(oc(da))gla)" the steps are da to ad, then ocad to daco, and finally the whole text, which gives "algocademy". The string has at most 2,000 characters.

    Approach: one buffer per nesting level

    Parentheses nest, and the innermost pair is handled first. That is the signature of a stack: the most recently opened level is the first one to close.

    Keep a stack of strings, where each string is the text collected so far at one nesting level. The bottom string holds the text outside every parenthesis. Then read the characters one by one:

    • On (, push a new empty string. A new level begins.
    • On ), pop the top string, reverse it, and append it to the string beneath, which is the level that contained this pair.
    • On any other character, append it to the top string.

    Reversing a level at the moment it closes is exactly the "innermost first" order. When a level is appended to its parent, the parent may itself be reversed later, which flips the already reversed text again. That is why "(u(love)i)" comes out right.

    Trace "(ab(cd)e)". The stack starts as [""]. After ( it is ["", ""], and after ab it is ["", "ab"]. Another ( gives ["", "ab", ""], and cd makes the top "cd". The ) pops "cd", reverses it to "dc" and appends it to "ab": ["", "abdc"]. Then e gives ["", "abdce"]. The last ) pops "abdce", reverses it to "ecdba" and appends it to the bottom string. The answer is "ecdba".

    Step by step

    1. Create the stack. Declare a vector<string> named res holding one empty string. The first string collects characters that appear before any opening parenthesis, and later it also receives finished levels.
    2. Loop over the characters of s with a range-based for and a char variable c.
    3. Handle (. Use push_back("") to open a new level.
    4. Handle ). This is the else if branch.
    5. Take the finished level. Copy res.back() into a string named top, and only then call pop_back(). back() returns a reference to the last element, and pop_back() destroys that element, so a reference would be left dangling.
    6. Reverse it with reverse(top.begin(), top.end()). The call changes the string in place, so no assignment is needed.
    7. Append it to the level below. After the pop, res.back() is the enclosing level. The += operator changes the string stored in the vector.
    8. Handle everything else. In the else branch, append c to res.back().
    9. Join and return. For balanced input exactly one string remains, but accumulate from string() concatenates whatever is left.

    The solution in C++

    class Solution {
public:
    string reverseParentheses(string s) {
        vector<string> res = {""};
        for (char c : s) {
            if (c == '(') {
                res.push_back("");
            } else if (c == ')') {
                string top = res.back();
                res.pop_back();
                reverse(top.begin(), top.end());
                res.back() += top;
            } else {
                res.back() += c;
            }
        }
        return accumulate(res.begin(), res.end(), string());
    }
};

    The C++ details worth knowing:

    • A vector works as a stack. push_back, back and pop_back are the push, peek and pop operations. std::stack would also work, but a vector allows the final loop over every entry.
    • Brace initialization. vector<string> res = {""} creates a vector with one empty string. Writing vector<string> res(1) would do the same.
    • Copy before pop. string top = res.back(); makes a copy, so top stays valid after pop_back(). Writing string& top = res.back(); and then popping would leave top referring to a destroyed string, and using it is undefined behaviour.
    • accumulate lives in <numeric>. Its third argument gives the starting value and its type. string() makes the accumulator a string. Passing "" instead makes the accumulator a const char*, and the code doesn't compile, because a string can't be assigned to one.
    • reverse lives in <algorithm>. It reverses the elements of the range it is given, here the characters of top.
    • Character against string. '(' is a char, and "" is a string. Comparing c == '(' uses single quotes, and res.back() += c appends one character.

    Complexity

    Let n be the length of s.

    Time: O(n²) in the worst case. Each character is read once, but a closing parenthesis copies, reverses and appends a whole level. For input such as (a(a(a(a)))), the text carried up to the parent grows by one character at each level, and every closing parenthesis reverses and copies it again, so the total work grows quadratically. With n at most 2,000 that is well within limits. For typical inputs it is close to linear.

    Space: O(n). The stack holds at most the characters of the string, plus the temporary top.

    Edge cases and common mistakes

    • No parentheses. "abc" stays "abc", since everything lands in the first string.
    • Text around a pair. "a(bc)d" gives "acbd". Only the part inside the pair is reversed.
    • Several pairs side by side. "(a)(bc)" gives "acb". Each pair is reversed on its own and appended in order.
    • Nested pairs that cancel. "((ab))" gives "ab", since the text is reversed twice.
    • An empty pair. "()" gives an empty string.
    • Reversing the wrong buffer. Reversing res.back() after the pop would reverse the parent level instead of the closed one.
    • Appending top before the pop. The text would go to the level that is about to disappear, and the result would be lost.

    Testing

    • "(abcd)" gives "dcba".
    • "(u(love)i)" gives "iloveu".
    • "(yme(oc(da))gla)" gives "algocademy".
    • "a(bc)d" gives "acbd".
    • "(a)(bc)" gives "acb".
    Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free