Start learning free

LESSON 293 OF 338 · STACK

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

    GO · STACK

    Reverse Substrings Between Each Pair Of Parentheses in Go, explained

    Problem overview

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

    In "(u(love)i)" the innermost pair holds love, which becomes evol. The string is now "(uevoli)", and reversing the outer pair gives "iloveu". In "(yme(oc(da))gla)" the innermost pair da becomes ad. The next pair then holds ocad, which reverses to daco. The outer pair holds ymedacogla, and reversing it gives "algocademy". The string has at most 2000 characters, and all parentheses are balanced.

    Approach: one buffer per nesting level

    Reversing from the inside out can be done in a single left-to-right pass if every open parenthesis gets its own text buffer. The buffers form a stack:

    • A letter is added to the buffer on top, the innermost group being read right now.
    • A ( pushes a new empty buffer.
    • A ) finishes the top buffer. Reverse it, pop it, and append it to the buffer below, which is the group that contained it.

    The reversal happens exactly when a group closes, so inner groups are always reversed before outer ones. By the time an outer ) arrives, its buffer already holds the inner results in their final shape, and reversing it flips them again, as the rules require.

    The alternative, finding the innermost pair, reversing it in place and repeating, rescans the string for every pair. The stack handles each character once, plus the cost of copying and reversing buffers when groups close.

    Step by step

    1. Start with one empty buffer. res := []string{""} is the stack. The first buffer collects the characters that sit outside every pair of parentheses.
    2. Loop over the string with for _, c := range s. Ranging over a string yields runes, and _ discards the byte index.
    3. Open a group. On '(', append an empty string to res.
    4. Add the else if for ')', on the same line as the closing brace.
    5. Close a group. Convert the last buffer to a []rune named top and drop it from the stack by reslicing.
    6. Reverse top with slices.Reverse, which works in place.
    7. Fold it into the level below. After the pop, the last entry of res is the enclosing buffer, so append string(top) to it.
    8. Any other character goes in the final else: append string(c) to the last buffer.
    9. Join what is left with strings.Join(res, "") and return it. For balanced input only one buffer remains.

    The solution in Go

    func reverseParentheses(s string) string {
    res := []string{""}
    for _, c := range s {
        if c == '(' {
            res = append(res, "")
        } else if c == ')' {
            top := []rune(res[len(res)-1])
            res = res[:len(res)-1]
            slices.Reverse(top)
            res[len(res)-1] += string(top)
        } else {
            res[len(res)-1] += string(c)
        }
    }
    return strings.Join(res, "")
}

    The solution uses the slices and strings packages. The Go details worth a closer look:

    • Strings are immutable. A string can't be reversed in place, so the buffer is converted to a []rune, which is a mutable slice. string(top) converts it back.
    • Runes, not bytes. range over a string decodes UTF-8 and gives runes, so c compares directly with '('. Reversing runes rather than bytes would also keep multi-byte characters intact, although this problem only has ASCII letters.
    • string(c) on a rune produces the one-character string: for the rune 97 it gives "a", not "97".
    • Compound assignment on an element. res[len(res)-1] += ... builds a new string and stores it back in the last slot of the slice.
    • Popping. res[:len(res)-1] shortens the slice without copying. The value was read into top first, so nothing is lost.
    • slices.Reverse comes from the standard slices package, available since Go 1.21. It returns nothing; it changes its argument.

    Complexity

    Time: O(n²) in the worst case. Each character is read once, but a closing parenthesis copies and reverses a whole buffer, and many nested pairs around one long run of letters copy that run again at every level. With n up to 2000 that cost is negligible. Appending to a string with += also copies the string, which adds to the same bound.

    Space: O(n). The buffers together never hold more than the letters of the input, plus short-lived copies when a group closes.

    Edge cases and common mistakes

    • No parentheses. "abc" stays in the first buffer and comes back unchanged.
    • Text around a group. "ab(cd)ef" gives "abdcef". The letters before the group live in the lower buffer, which is why a group is appended to it rather than replacing it.
    • Sibling groups. "(ab)(cd)" gives "badc": each group is reversed on its own, and they are not reversed together.
    • Two levels of reversal. "a(b(c)d)e" gives "adcbe". The inner c reads the same either way, and the outer buffer bcd reverses to dcb.
    • Reversing a string directly. Go has no string reverse and strings can't be assigned by index, so s[i] = x doesn't compile. Convert to []rune first.
    • Forgetting to pop before appending. The folded text must go to the buffer below the one just closed. Reslicing before the append makes res[len(res)-1] point to that buffer.

    Testing

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