Start learning free

LESSON 296 OF 344 · STACK

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

    PYTHON · STACK

    Reverse Substrings Between Each Pair Of Parentheses in Python, 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, starting with the innermost pair, and the result must contain no parentheses.

    For "(u(love)i)" the inner pair holds love, which becomes evol. The string is now (uevoli), and reversing the outer pair gives iloveu. For "(yme(oc(da))gla)" the steps are da to ad, then ocad to daco, then the whole content ymedacogla to algocademy.

    Approach: one buffer per open parenthesis

    The innermost-first rule is a signal for a stack. Every ( starts a new level of text, and the matching ) ends the most recently opened one, so the last level opened is the first one closed.

    Keep a stack where each item is a string buffer collecting the characters of one level. Ordinary letters go to the buffer on top. When a ( arrives, push a new empty buffer. When a ) arrives, pop the top buffer, reverse it, and append it to the buffer that is now on top, because that text belongs to the enclosing level. Reversal happens at the moment a level closes, so inner levels are reversed before the outer ones that contain them. This gives exactly the order the problem asks for.

    Here is the stack for "(u(love)i)" after each character:

    CharacterStack afterwards
    (['', '']
    u['', 'u']
    (['', 'u', '']
    l, o, v, e['', 'u', 'love']
    )['', 'uevol']
    i['', 'uevoli']
    )['iloveu']

    Step by step

    1. Start with one empty buffer. res = ['']. The bottom buffer collects characters that sit outside every pair of parentheses, so the stack is never empty while the loop runs.
    2. Loop over the characters of s with the variable c.
    3. Open a level on (. Append '' to res. Everything up to the matching ) will be collected in it.
    4. Handle ) in an elif. This branch closes the level on top.
    5. Pop the top buffer with res.pop() into top. It is the text between the parentheses just closed.
    6. Reverse it with the slice top[::-1] and call the result reversed_top.
    7. Append it to the new top, res[-1] += reversed_top. After the pop, the enclosing level's buffer is last, and the reversed text is part of it.
    8. Handle every other character in the else branch: res[-1] += c adds it to the current level.
    9. Join and return. "".join(res) combines the buffers. For balanced input only the bottom buffer remains, so the join returns that single string.

    The solution in Python

    class Solution:
    def reverseParentheses(self, s: str) -> str:
        res = ['']
        for c in s:
            if c == '(':
                res.append('')
            elif c == ')':
                top = res.pop()
                reversed_top = top[::-1]
                res[-1] += reversed_top
            else:
                res[-1] += c
        return "".join(res)

    Python details to notice:

    • A list works as a stack. append pushes at the end, pop() without an argument removes and returns the last item, and res[-1] reads the top without removing it.
    • Slicing with step -1. top[::-1] walks the string backwards and returns a new string. Python has no reverse() method on strings, so a slice (or "".join(reversed(top))) is the usual way.
    • Strings are immutable. res[-1] += c builds a new string and stores it back into that slot of the list. The old string is not changed in place.
    • "".join(res) joins the strings with nothing between them. It is the standard way to combine a list of strings.

    Complexity

    Time: O(n²) in the worst case, where n is the length of s. Every ) reverses a buffer and copies it into the buffer below, so the work per closing parenthesis is the length of the text inside. When pairs are nested, the same letters are copied again at every level. Take 500 opening parentheses, then 1,000 letters, then 500 closing parentheses: each of the 500 closings copies a buffer of 1,000 letters, which is about 500,000 character copies. Ordinary strings are far cheaper, and with the limit of 2,000 characters even this worst case runs instantly.

    Space: O(n). The buffers together hold at most all the letters of the string.

    Edge cases and common mistakes

    • No parentheses. "abc" stays "abc", since everything goes into the bottom buffer.
    • Text outside the pair. "a(bc)d" gives "acbd". The letters a and d remain in place around the reversed part.
    • Side-by-side pairs. "(ab)(cd)" gives "badc". Each pair is reversed alone, and the pairs keep their order.
    • An empty pair. "()" gives the empty string.
    • Appending to the wrong buffer. After popping, the reversed text must go to res[-1]. Putting it back with a push would keep the level open.
    • Reversing the whole string at the end. That only works for a single outer pair. The reversal must happen once per closing parenthesis, on the level that just closed.
    • Forgetting the bottom buffer. With res = [], the first letter outside any parentheses would hit res[-1] on an empty list and raise IndexError.

    Testing

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