Start learning free

LESSON 300 OF 348 · STACK

Reverse Substrings Between Parentheses in TypeScript: Stack of Buffers

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

    TYPESCRIPT · STACK

    Reverse Substrings Between Each Pair Of Parentheses in TypeScript, explained

    Problem overview

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

    Take "(u(love)i)". The innermost pair holds love, which becomes evol. The string is now (uevoli). Reversing the outer pair turns uevoli into iloveu, so the answer is "iloveu". The deepest example, "(yme(oc(da))gla)", goes through three reversals: da becomes ad, then ocad becomes daco, and finally the whole text becomes algocademy.

    Approach: one buffer per nesting level

    The simplest idea is to find the innermost pair, reverse it, delete its parentheses and repeat. That rescans the string many times and shifts characters around on every round. A single left-to-right pass is cleaner.

    Think of each ( as opening a fresh piece of paper. Every letter you read is written on the top piece. When a ) arrives, the top piece is complete: reverse it, throw the paper away and write the reversed text onto the piece underneath. That piece may itself be inside parentheses, and it will be reversed later, together with everything written on it. This is exactly the "innermost first" order the task asks for.

    A stack gives you this behaviour: the most recently opened level is always the first one closed. Here the stack holds strings, one per open level, and the bottom one collects the text that sits outside every pair.

    For "a(bc)d" the stack changes like this:

    a  ["a"]
(  ["a", ""]
b  ["a", "b"]
c  ["a", "bc"]
)  ["acb"]
d  ["acbd"]

    Each character is handled once, so the pass is fast. The only repeated work is reversing each buffer when its level closes.

    Step by step

    1. Create the stack as an array of strings holding one empty string. That first entry collects characters that appear before any (. It is a const because the array's contents change but the variable is never reassigned.
    2. Loop over the characters with for...of, which gives you one character per iteration.
    3. On (, push an empty string. A new level starts and collects everything until its matching ).
    4. On ), pop the top buffer. It holds exactly the text between the parentheses being closed.
    5. Reverse that text. Strings have no reverse method, so split it into an array of characters, reverse the array and join it back.
    6. Append the reversed text to the buffer that is now on top. After the pop, that is the level one step out.
    7. On any other character, append it to the top buffer.
    8. Join the buffers and return the result. For balanced input only one buffer remains, so joining just returns it.

    The solution in TypeScript

    class Solution {
    reverseParentheses(s: string): string {
        const res: string[] = [""];
        for (const c of s) {
            if (c === "(") {
                res.push("");
            } else if (c === ")") {
                const top = res.pop();
                const reversedTop = top.split("").reverse().join("");
                res[res.length - 1] += reversedTop;
            } else {
                res[res.length - 1] += c;
            }
        }
        return res.join("");
    }
}

    The TypeScript details worth a closer look:

    • The type of pop(). An array's pop() returns the removed element, or undefined when the array is empty. Because the input is guaranteed balanced, a ) always has a buffer to pop. The lesson compiles with strict null checking off, so top is treated as a plain string.
    • Strings are immutable. res[res.length - 1] += c builds a new string and stores it back into that slot of the array. It doesn't modify the old string.
    • const and arrays. const res stops you from assigning a different array to res. It doesn't stop push, pop or writing to res[i].
    • for...of on a string. It walks the string one character at a time, so c is a one-character string and the comparison c === "(" is a plain string comparison.
    • Annotations are not checked at run time. The : string[] annotation helps the compiler and the editor, but the compiled JavaScript contains no types at all.

    Complexity

    Let n be the length of s.

    Time: O(n²) in the worst case. Each character is appended once when it is read. But a character inside k nested pairs is copied again each time one of those pairs closes, once for the reversal and once for the append. A string such as ((((ab)))) therefore copies its letters at every level, and a deeply nested input makes the total grow with the square of its length. With n up to 2000, this is comfortably fast.

    Space: O(n). The buffers together never hold more than the letters of the input, plus the temporary arrays created by split.

    Edge cases and common mistakes

    • No parentheses. "ab" stays "ab", because everything lands in the first buffer.
    • Text around a pair. "a(bc)d" gives "acbd": only the part inside the parentheses is reversed.
    • Side-by-side pairs. "(ab)(cd)" gives "badc". Each pair is reversed on its own, and the pairs are not swapped with each other.
    • Reversing once at the end. Reversing the whole string once is not the same as reversing level by level. Each pair must be reversed at the moment it closes.
    • Writing to the wrong buffer. After the pop, append to res[res.length - 1], the new top. Appending to the popped one loses the text.
    • Calling reverse() on a string. "abc".reverse() is a type error, because only arrays have that method. Go through split("") and join("").

    Testing

    • "(abcd)" gives "dcba".
    • "(u(love)i)" gives "iloveu".
    • "(yme(oc(da))gla)" gives "algocademy".
    • "a(b(c)d)e" gives "adcbe".
    • "ab" gives "ab".
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free