Start learning free

LESSON 324 OF 414 · STACK

Reverse Substrings Between Each Pair of Parentheses in Scala

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:

  • The length of s is between 1 and 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

    SCALA · STACK

    Reverse Substrings Between Each Pair Of Parentheses in Scala, explained

    Problem overview

    The method reverseParentheses receives a string s made of lowercase letters and balanced parentheses. It reverses the text inside every pair of matching parentheses, starting with the innermost pair, and returns the result without any parentheses.

    For "(u(love)i)" the innermost pair holds "love", which becomes "evol", so the string is now "(uevoli)". Reversing that whole group gives "iloveu". For "(yme(oc(da))gla)" the steps are "da" to "ad", then "ocad" to "daco", then the outer group "ymedacogla" to "algocademy".

    Approach: one buffer per nesting level

    The text inside a pair of parentheses can be finished only when its closing parenthesis arrives. Until then it may still receive more characters or inner groups. So keep a stack of strings, one for each level of nesting that is currently open. The last string on the stack collects characters for the innermost open group.

    • On (, open a new level: push an empty string.
    • On a letter, append it to the last string.
    • On ), the last string is complete. Remove it, reverse it and append the result to the string below it, which is the enclosing level.

    Reversing happens as each group closes, so inner groups are reversed before the outer ones that contain them, which is the order the problem asks for. At the start the stack holds one empty string, the base level that collects the text outside every pair.

    Take "a(bc(de)f)g". The stack changes like this, after each character:

    a  ["a"]
(  ["a", ""]
b  ["a", "b"]
c  ["a", "bc"]
(  ["a", "bc", ""]
d  ["a", "bc", "d"]
e  ["a", "bc", "de"]
)  ["a", "bced"]
f  ["a", "bcedf"]
)  ["afdecb"]
g  ["afdecbg"]

    The first ) reverses "de" and appends "ed" to "bc". The second reverses "bcedf" and appends "fdecb" to "a".

    Step by step

    1. Create the stack as val res, an ArrayBuffer[String] holding one empty string. An ArrayBuffer can grow and shrink, and its last element is the top of the stack.
    2. Loop over the characters with for (c <- s). A String can be used directly as a sequence of Char values.
    3. Handle (. Append an empty string with res += "" to start a new level.
    4. Handle ). Remove the last element with res.remove(res.length - 1), which returns the removed string, and keep it in top.
    5. Reverse it with top.reverse.
    6. Merge it downwards. After the removal, the enclosing level is the last element, so set res(res.length - 1) to its old value plus the reversed text.
    7. Handle every other character by appending it to the last element in the same way.
    8. Join the buffers with mkString("") and return the result. For balanced input only the base level is left, so the join returns that single string.

    The solution in Scala

    class Solution {
    def reverseParentheses(s: String): String = {
        val res = scala.collection.mutable.ArrayBuffer[String]("")
        for (c <- s) {
            if (c == '(') {
                res += ""
            } else if (c == ')') {
                val top = res.remove(res.length - 1)
                val reversedTop = top.reverse
                res(res.length - 1) = res(res.length - 1) + reversedTop
            } else {
                res(res.length - 1) = res(res.length - 1) + c
            }
        }
        return res.mkString("")
    }
}

    Scala details:

    • val fixes the reference, not the contents. res can't be reassigned, but its buffer can still grow, shrink and have elements replaced.
    • res(i) = value calls update on the buffer, and res(i) reads with apply. Both use parentheses, not square brackets.
    • remove(index) returns the element it removes. That is why one call both takes the top string and shortens the stack.
    • reverse on a String takes no parentheses and returns a new string. Strings are immutable, so the original is unchanged.
    • String plus Char. res(res.length - 1) + c appends the character and gives a new string. Each append copies the string, which is acceptable for a limit of 2000 characters.
    • The return keyword is optional on the last line. It is legal here because it is not inside a closure: the loop body is a function passed to foreach, and a return inside it would leave the method from within that function.

    Complexity

    Time: O(n^2) in the worst case. Every character is handled once, but appending a character to a string copies the string, so building one group of k characters costs about k^2 / 2 copied characters. Reversing and merging a group copies it again at each closing parenthesis, and a deeply nested input copies its inner text once per level. With n at most 2000 this is far below any limit.

    Space: O(n). All the buffers together hold at most the characters of the input, and the stack has at most one entry per open parenthesis plus one.

    Edge cases and common mistakes

    • No parentheses. "abc" returns "abc": only the base level exists.
    • Text outside the pairs stays in place. "ab(cd)ef" returns "abdcef".
    • Sibling groups. "a(bc)(de)f" returns "acbedf". Each group is reversed on its own, and the groups are not reversed relative to each other.
    • Double parentheses. "((a))" returns "a": the single letter is reversed twice.
    • Nested groups. "a(b(c)d)e" returns "adcbe". Reversing "c" changes nothing, so the outer group holds "bcd", which is reversed to "dcb".
    • Reversing at the wrong time. Reversing the buffer on ( or at the end of the loop instead of on ) gives wrong answers for nested groups, because an inner group must be finished before the outer one that contains it.
    • Dropping the base level. Without the initial empty string, a letter before the first ( would have no buffer to go into.

    Testing

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