Start learning free

LESSON 300 OF 348 · STACK

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

    KOTLIN · STACK

    Reverse Substrings Between Each Pair Of Parentheses in Kotlin, explained

    Problem overview

    The function reverseParentheses receives a string s made 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 a result that contains no parentheses at all.

    Take "(u(love)i)". The innermost pair holds love, which becomes evol. The outer pair now holds uevoli, and reversing that gives iloveu. The last example, "(yme(oc(da))gla)", nests three levels deep: da becomes ad, then ocad becomes daco, and finally ymedacogla becomes algocademy. The input has between 1 and 2000 characters and the parentheses are always balanced.

    Approach: one buffer per nesting level

    A direct plan is to find the innermost pair, reverse it, delete its parentheses and repeat. That works, but it rescans the string many times. A single left-to-right pass is simpler if you notice that parentheses behave like a stack: the pair that closes first is always the one that opened last.

    Keep a stack of text buffers, one per open parenthesis, plus a base buffer for text outside any parenthesis. Then the rules are:

    • A letter is appended to the buffer on top of the stack.
    • An opening parenthesis pushes a new, empty buffer. Everything up to the matching closing parenthesis is collected there.
    • A closing parenthesis pops the top buffer, reverses it, and appends the reversed text to the buffer below. That buffer was the enclosing level, which is exactly where the text belongs once its own pair is resolved.

    The innermost-first order falls out for free. By the time a ) arrives, every pair nested inside it has already been popped, reversed and merged into the buffer that is now being reversed.

    For "(u(love)i)" the stack evolves like this, one buffer per entry:

    start   [""]
(       ["", ""]
u       ["", "u"]
(       ["", "u", ""]
love    ["", "u", "love"]
)       ["", "uevol"]
i       ["", "uevoli"]
)       ["iloveu"]

    One buffer remains at the end, and it is the answer.

    Step by step

    1. Create the stack. It starts with one empty string, the base buffer for characters outside every parenthesis. Because it is never removed for balanced input, the stack is never empty while the loop runs.
    2. Loop over the characters of s in order, naming each one c.
    3. Handle (. Push an empty string to open a new level.
    4. Handle ). This branch does three things, one per step: pop the top buffer, reverse it, and merge it into the new top.
    5. Pop the finished buffer. The removal returns the removed element, so the same line stores it in top.
    6. Reverse it into reversedTop. The original string is untouched, because the operation builds a new one.
    7. Append to the level below. After the pop, the enclosing level is the last element. Strings can't be changed in place, so the concatenation is assigned back to that slot.
    8. Handle every other character. It is a letter, so append it to the last buffer in the same way.
    9. Join and return. For balanced input only the base buffer is left. Joining with an empty separator turns the list into one string, and it also copes if more than one entry were ever left.

    The solution in Kotlin

    class Solution {
    fun reverseParentheses(s: String): String {
        val res = mutableListOf("")
        for (c in s) {
            if (c == '(') {
                res.add("")
            } else if (c == ')') {
                val top = res.removeAt(res.size - 1)
                val reversedTop = top.reversed()
                res[res.size - 1] = res[res.size - 1] + reversedTop
            } else {
                res[res.size - 1] = res[res.size - 1] + c
            }
        }
        return res.joinToString("")
    }
}

    The Kotlin details worth knowing:

    • val does not freeze the list. val res means the name res can't be pointed at another list. The list is a MutableList<String>, so add, removeAt and element assignment all work. The type is inferred from mutableListOf("").
    • Strings are immutable. There is no way to append to the string inside the list. res[res.size - 1] = ... replaces the element with a new string. Writing res[res.size - 1] += c does the same thing.
    • String + Char works. Kotlin's plus accepts any value on the right, so "ab" + 'c' is "abc" without a conversion.
    • Iterating a string. for (c in s) yields each Char in turn. Compare it with single quotes: '(' is a Char, while "(" would be a String and the comparison c == "(" would not compile.
    • reversed() returns a new string. Called on a String it gives back a String, and the original is unchanged. That is why the result is stored in reversedTop.
    • joinToString has a default separator. With no argument it puts ", " between entries, so listOf("a", "b").joinToString() is "a, b". Passing "" glues the entries together.
    • if / else if / else chain. Only one branch runs for each character, and the final else covers every character that is neither parenthesis.

    Complexity

    Let n be the length of s.

    Time: O(n * d), at most O(n²), where d is the nesting depth. Every character is visited once, but each append copies the buffer it extends, and a character inside several nested pairs is reversed once per enclosing pair. For a worst case like ((((...)))) the total work grows quadratically. With n capped at 2000 that is a few million character operations, which is fine.

    Space: O(n). All buffers together hold at most the characters of the input, plus the short-lived copies made by concatenation and reversal.

    Edge cases and common mistakes

    • No parentheses. "abc" never touches the stack beyond the base buffer and comes back unchanged.
    • Adjacent pairs. "a(bc)(de)f" gives "acbedf". Each pair is reversed separately and the pieces stay in their original order.
    • Nested pairs around the same text. "((a))" gives "a": reversing a single letter twice changes nothing. A segment reversed an even number of times ends up in its original order.
    • Text on both sides of a pair. "ab(cd)ef" gives "abdcef". Only the inside of the parentheses is reversed.
    • Forgetting to merge the reversed buffer. If the popped buffer is reversed but never appended to the level below, the letters inside parentheses vanish from the result.
    • Reversing the whole string. A single reverse at the end is wrong. With three nested levels the innermost text is reversed three times, and the depth of each part decides the final order.
    • Keeping the parentheses. Parentheses must never be added to a buffer. In this solution they only push and pop, so none reach the result.

    Testing

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