Start learning free

LESSON 325 OF 414 · STACK

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

  • 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

    RUST · STACK

    Reverse Substrings Between Each Pair Of Parentheses in Rust, explained

    Problem overview

    The function reverse_parentheses receives a string s made of lowercase letters and balanced parentheses. It must reverse the text inside every pair of matching parentheses, starting with the innermost pair, and return the result without any parentheses.

    For "(u(love)i)" the inner text love is reversed first and becomes evol, so the string reads (uevoli). Reversing that outer pair gives iloveu. For "(yme(oc(da))gla)" the steps are da to ad, then ocad to daco, then the whole ymedacogla to algocademy. The string has at most 2,000 characters and the parentheses are always balanced.

    Approach: one buffer per nesting level

    A direct approach finds the innermost pair, reverses the text between its parentheses, removes the parentheses and repeats. Each round scans the string, and there can be about n / 2 rounds, so this costs O(n²). With at most 2,000 characters that would still run, but there is a cleaner way that reads the string once.

    The key observation is that the innermost group is always the most recently opened one. That is exactly what a stack models. Keep a stack of text buffers, one per open parenthesis, plus one base buffer for the text outside every parenthesis:

    • A letter is appended to the buffer on top of the stack.
    • An opening parenthesis pushes a new empty buffer. Everything up to its matching ) is collected there.
    • A closing parenthesis ends the top buffer. Its text is complete, so it is reversed, removed from the stack and appended to the buffer below it, which is the level that contained the group.

    Reversal happens once per pair, at the moment the pair closes. By then any inner pairs inside it have been reversed and merged already, which is what "innermost first" means. The base buffer ends up holding the final answer.

    On "(u(love)i)" the stack evolves like this:

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

    Step by step

    1. Create the stack res as a Vec<String> that already holds one empty string. That string is the base level that collects the characters outside any parentheses, so the stack is never empty while the input is balanced.
    2. Loop over the characters with s.chars(), using the loop variable c.
    3. Handle (. Push a new empty String, which opens a nesting level.
    4. Handle ) with an else if. The next three steps live in this branch.
    5. Copy the closed buffer into a Vec<char> named top, then remove it from the stack with pop(). A vector of characters can be reversed in place.
    6. Reverse top with reverse().
    7. Append it to the level below: collect the characters back into a String and add it with push_str to the last buffer. After the removal, the last buffer is the enclosing one.
    8. Handle any other character with a final else by pushing c onto the last buffer.
    9. Return res.concat() after the loop. For balanced input only the base buffer is left, and concat joins the buffers into one String.

    The solution in Rust

    impl Solution {
    fn reverse_parentheses(s: String) -> String {
        let mut res: Vec<String> = vec![String::new()];
        for c in s.chars() {
            if c == '(' {
                res.push(String::new());
            } else if c == ')' {
                let mut top: Vec<char> = res[res.len() - 1].chars().collect();
                res.pop();
                top.reverse();
                res.last_mut().unwrap().push_str(&top.into_iter().collect::<String>());
            } else {
                res.last_mut().unwrap().push(c);
            }
        }
        res.concat()
    }
}

    Rust details that matter here:

    • Why Vec<char>. A String has no in-place reverse method, and reversing its bytes would break any multi-byte character. chars() yields Unicode characters, so collecting them into a Vec<char> and calling reverse() is correct. The input here is plain lowercase letters, but the approach does not depend on that.
    • Reading before popping. res[res.len() - 1] reads the last buffer, and chars().collect() makes a new vector, so top does not borrow from res. That is why res.pop() is allowed on the next line. The popped String is simply discarded.
    • last_mut().unwrap(). last_mut() returns an Option<&mut String>, which is None only for an empty stack. The base buffer is never popped for balanced input, so unwrap() is safe. The resulting mutable reference is used for a single call, push or push_str.
    • push and push_str. push adds one char, and push_str adds a string slice. That is why the collected String is passed as &..., which borrows it as a &str.
    • into_iter().collect::<String>(). The turbofish names the type to build. Vec<char> implements into_iter over owned characters, and String can be built from an iterator of char.
    • Tail expression. res.concat() has no semicolon, so it is the function's return value.

    Complexity

    Time: O(n²) in the worst case. Each character is appended once when it is read. But a closing parenthesis copies and reverses its whole buffer, and text that sits inside many levels of nesting is copied again at every level it passes through. A string with a few hundred letters wrapped in hundreds of pairs copies those letters once per pair. For the 2,000-character limit this is small. A linear solution exists, which records matching parenthesis positions and walks the string while switching direction, but the stack of buffers is easier to get right.

    Space: O(n). The buffers together hold at most the characters of the input, and top is a temporary copy of one buffer.

    Edge cases and common mistakes

    • No parentheses. "abc" stays abc. All letters go into the base buffer.
    • Text around a group. "a(bc)d" gives acbd. Only the part in parentheses is reversed, and the base buffer keeps the surrounding letters in order.
    • Several groups side by side. "(ab)(cd)" gives badc. Each pair is reversed on its own, and the results are joined in the original order.
    • Double reversal. "((ab))" gives ab, because the text is reversed twice, once by each pair.
    • Mixed nesting. "(a(b)c)(d)" gives cbad. The inner b reverses to itself, abc reverses to cba, and d follows.
    • Appending to the wrong level. The reversed text belongs to the buffer below the closed one. Appending before the pop() would put it into the buffer that is about to be discarded.
    • Forgetting the base buffer. Without the initial empty string, the first letter outside any parentheses would find an empty stack, and unwrap() would panic.

    Testing

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