Start learning free

LESSON 296 OF 344 · STACK

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

    JAVA · STACK

    Reverse Substrings Between Each Pair Of Parentheses in Java, explained

    Problem overview

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

    For "(abcd)" the answer is "dcba". For "(u(love)i)", first love is reversed to evol, giving (uevoli), and then the whole group is reversed, giving "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

    Each pair of parentheses opens a new nesting level, and the text in it is finished when its closing parenthesis arrives. At that moment you reverse the text and treat it as ordinary text of the level outside. This is last-in, first-out behaviour: the most recently opened level is the first one to close. A stack fits.

    The lesson keeps a stack of strings, one per open level, with the current level on top:

    • The stack starts with one empty string for the text before any parenthesis.
    • An opening parenthesis pushes a new empty string.
    • A closing parenthesis pops the top string, reverses it, and appends it to the string below.
    • Any letter is appended to the top string.

    When the input has been read, the stack holds one string, the answer. Reading "a(bc)d": the buffer holds a. The ( adds a second buffer, which collects bc. The ) removes it, reverses it to cb and appends it to the first buffer, giving acb. The letter d then makes it acbd.

    Because inner groups are reversed when they close, and the result is added to the outer buffer, the outer group sees already-reversed text. When the outer group closes, the whole buffer is reversed again, which is exactly the "innermost first" order the statement describes.

    Step by step

    1. Create the stack. A List<String> named res, built as an ArrayList from List.of(""). It starts with one empty string. List.of alone returns an unmodifiable list, so the copy into an ArrayList is what lets the list grow and shrink.
    2. Loop over the characters with for (char c : s.toCharArray()).
    3. On (, add an empty string. It collects the text up to the matching ).
    4. On ), remove the last element, at index res.size() - 1, into top. This is the group being closed.
    5. Reverse it. Wrap top in a StringBuilder, call reverse() and convert back with toString(), giving reversedTop.
    6. Merge it downward. After the removal, the buffer for the enclosing level is the last element. Replace it, using set, with its old value plus reversedTop.
    7. On any other character, append it to the last element the same way, with set and get.
    8. Return the joined stack. String.join("", res) concatenates the entries with an empty separator. For balanced input only one entry remains, so this returns it.

    The solution in Java

    class Solution {
    public String reverseParentheses(String s) {
        List<String> res = new ArrayList<>(List.of(""));
        for (char c : s.toCharArray()) {
            if (c == '(') {
                res.add("");
            } else if (c == ')') {
                String top = res.remove(res.size() - 1);
                String reversedTop = new StringBuilder(top).reverse().toString();
                res.set(res.size() - 1, res.get(res.size() - 1) + reversedTop);
            } else {
                res.set(res.size() - 1, res.get(res.size() - 1) + c);
            }
        }
        return String.join("", res);
    }
}

    The Java details worth a closer look:

    • Strings are immutable. You can't change a character of a String or append to it in place. The expression res.get(i) + c builds a new string, and set stores that new string in the list, replacing the old one. Calling get alone and adding would change nothing in the list.
    • remove takes an index here. res is a List<String>, so res.remove(res.size() - 1) passes an int and removes the element at that position, returning it. The other overload, remove(Object), removes the first matching value. With a List<Integer> the two could be confused.
    • String + char appends the character. Adding a char to a String uses string concatenation, so "ab" + 'c' is "abc". It would add numbers if you added a char to an int.
    • No reverse on String. StringBuilder has a reverse() method. It reverses in place and returns the same builder, so chaining .toString() gives the reversed string.
    • Comparing chars. c == '(' compares two primitive char values with ==, which is correct. Characters use single quotes and strings use double quotes.
    • The stack is a list. ArrayList adds and removes at its end in constant time, so the last element serves as the stack's top. Deque is a common alternative.

    Complexity

    Let n be the length of s.

    Time: O(n²) in the worst case. Each letter is appended by building a new string, which copies the buffer. Each closing parenthesis reverses and copies a buffer too. A buffer holds at most n characters, and there are at most n such operations. With n up to 2,000 this is a few million character copies, which is fast.

    Space: O(n). The buffers together hold at most n characters, plus temporary copies of one buffer at a time.

    Edge cases and common mistakes

    • No parentheses. "abc" returns "abc". Only the first buffer is ever used.
    • Nested groups. "((ab))" is reversed twice and returns "ab".
    • Adjacent groups. "(ab)(cd)" returns "badc". Each group is reversed on its own, and the results are joined in order.
    • An empty pair. "a()b" returns "ab". The empty buffer is reversed to an empty string and appended.
    • Deep nesting. A thousand nested pairs around one letter work, since the stack is a heap-allocated list and no recursion is used.
    • Reversing the wrong buffer. The reversal applies to the string just removed, not to the enclosing one.
    • Forgetting to store back. Writing res.get(res.size() - 1) + c as a statement computes a string and throws it away.

    Testing

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