Reverse Substrings Between Each Pair of Parentheses

medium stack string parentheses

Problem

You are given a string s that consists of lowercase letters and brackets. Reverse the strings in each pair of matching parentheses, starting from the innermost one. The result should not contain any brackets.

Inputs = "(u(love)i)"

Output"iloveu"

The innermost "love" stays, then "u" + "love" + "i" is reversed to "iloveu".

s (lowercase letters and parentheses)

def reverse_parentheses(s):
    stack = [""]
    for ch in s:
        if ch == "(":
            stack.append("")
        elif ch == ")":
            inner = stack.pop()
            stack[-1] += inner[::-1]
        else:
            stack[-1] += ch
    return stack[0]

function reverseParentheses(s) {
  const stack = [""];
  for (const ch of s) {
    if (ch === "(") {
      stack.push("");
    } else if (ch === ")") {
      const inner = stack.pop();
      stack[stack.length - 1] += [...inner].reverse().join("");
    } else {
      stack[stack.length - 1] += ch;
    }
  }
  return stack[0];
}

class Solution {
    public String reverseParentheses(String s) {
        Deque<StringBuilder> stack = new ArrayDeque<>();
        stack.push(new StringBuilder());
        for (char ch : s.toCharArray()) {
            if (ch == '(') {
                stack.push(new StringBuilder());
            } else if (ch == ')') {
                StringBuilder inner = stack.pop().reverse();
                stack.peek().append(inner);
            } else {
                stack.peek().append(ch);
            }
        }
        return stack.peek().toString();
    }
}

string reverseParentheses(string s) {
    vector<string> stack(1, "");
    for (char ch : s) {
        if (ch == '(') {
            stack.push_back("");
        } else if (ch == ')') {
            string inner = stack.back();
            stack.pop_back();
            reverse(inner.begin(), inner.end());
            stack.back() += inner;
        } else {
            stack.back() += ch;
        }
    }
    return stack[0];
}

Explanation

Parentheses can be nested, and each pair reverses its contents. Rather than hunting for matching brackets, we keep a stack of string fragments, where each frame holds the text being built at the current nesting level.

We start with one empty frame for the top level. When we hit (, we open a new scope by pushing a fresh empty string. When we hit ), we pop the finished inner frame, reverse it, and append it to the frame now on top. For an ordinary letter, we just append it to the top frame.

This naturally handles nesting "from the inside out": an inner pair is closed (and reversed) before its surrounding pair, so by the time the outer ) reverses things, the inner part is already in its correct reversed-then-reversed form.

Example: s = "(u(love)i)". Inside the outer scope we build "u", then open a scope for "love". The inner ) reverses "love" → "evol" and appends it, giving "uevol", then "i" → "uevoli". The outer ) reverses that whole thing to "iloveu".

The single frame left at the bottom is the bracket-free answer.

Time: O(n) Space: O(n)