Start learning free

LESSON 296 OF 344 · STACK

Reverse Substrings Between Parentheses in JavaScript: 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

    JAVASCRIPT · STACK

    Reverse Substrings Between Each Pair Of Parentheses in JavaScript, explained

    Problem overview

    The method reverseParentheses receives a string s of lowercase letters and balanced parentheses. It must reverse the text inside each 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)", first love is reversed to evol, which makes the text inside the outer pair uevoli. Reversing that gives iloveu. For "(yme(oc(da))gla)" the steps are da to ad, then ocad to daco, and the outer text becomes ymedacogla, whose reverse is algocademy.

    Approach: one buffer per nesting level

    Parentheses nest, and the innermost pair has to be finished first. That is the behaviour of a stack: the last thing opened is the first thing closed. Use a stack of strings, where each string collects the characters of one nesting level.

    • The bottom buffer collects the characters outside any parentheses.
    • An opening ( starts a new level, so push an empty buffer.
    • An ordinary letter is appended to the buffer on top.
    • A closing ) ends the top level. Remove that buffer, reverse it, and append the reversed text to the buffer now on top, because that text belongs to the enclosing level.

    When the scan ends, only the bottom buffer is left, and it holds the finished answer.

    Take "(u(love)i)". The stack goes from [""] to ["", ""] at the first (, then ["", "u"] after the u. The second ( gives ["", "u", ""], and love fills the top buffer. At the first ), "love" is removed, reversed to "evol", and appended to "u", leaving ["", "uevol"]. Then i gives ["", "uevoli"]. The last ) removes "uevoli", reverses it to "iloveu" and appends it to the bottom buffer. The final stack is ["iloveu"].

    Step by step

    1. Create the stack. Declare res with const as an array holding one empty string. const is enough because the code changes the array's contents but never assigns a new array to res.
    2. Loop over the characters of s with for...of, naming each one c.
    3. Handle (. When c === "(", push an empty string. That opens a new level.
    4. Handle ). The next branch tests c === ")".
    5. Remove the finished level. pop() takes the top buffer off the stack and returns it. Store it in top.
    6. Reverse it. Strings have no reverse method, so convert with split("") into an array of characters, call reverse() on the array, and join it back with join(""). Store the result in reversedTop.
    7. Hand it to the level below. After the pop, the enclosing buffer is the last element, res[res.length - 1]. Append reversedTop to it with +=.
    8. Handle any other character. In the final else branch, append c to the top buffer in the same way.
    9. Return the answer. res.join("") joins all buffers into one string. With balanced input only one buffer is left, so joining returns that buffer unchanged, and it is also safe if extra levels remain.

    The solution in JavaScript

    class Solution {
    reverseParentheses(s) {
        const res = [""];
        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 JavaScript details worth a look:

    • An array as a stack. push adds to the end and pop removes from the end, both in constant time, so the end of the array is the top of the stack.
    • Strings are immutable. res[res.length - 1] += c doesn't change a string in place. It builds a new string and stores it back into that slot of the array.
    • Reversing a string. split(""), reverse(), join("") is the standard idiom. reverse() reverses the array in place, which is harmless here because the array is a temporary.
    • Iterating a string with for...of. It yields one character per step. For this lesson's lowercase letters that is the same as indexing, but for...of works on whole code points.
    • const with arrays. The binding can't be reassigned, yet the array it points to can still be changed.

    Complexity

    Let n be the length of s.

    Time: O(n²) in the worst case. Each character is appended once, but a closing parenthesis reverses its whole buffer. With deeply nested parentheses, like "((((abc))))", the same letters get reversed again at every level, so the work can add up to about n per level over n / 2 levels. With n at most 2000 this is tiny.

    Space: O(n). The buffers together never hold more than the characters of s, plus the temporary reversed copy.

    Edge cases and common mistakes

    • No parentheses. "abc" stays "abc", since everything goes into the bottom buffer.
    • Text around a pair. "a(bc)d" gives "acbd". The a and the d are in the bottom buffer on either side of the reversed text.
    • Empty parentheses. "()" gives an empty string, because an empty buffer reverses to an empty buffer.
    • Double wrapping. "((ab))" gives "ab". It is reversed twice, which cancels out.
    • Appending to the wrong buffer. After the pop, add the reversed text to the new top of the stack. Appending it before the pop would put it into the buffer that is about to be removed.
    • Calling reverse on a string. It doesn't exist and throws a TypeError. Convert to an array first.
    • Dropping the reversed text. Without the += the letters inside a pair vanish from the answer.

    Testing

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