Reverse Substrings Between Each Pair of Parentheses

Medium
390.

Reverse Substrings Between Each Pair of Parentheses

Reverse Substrings Between Each Pair of Parentheses is a medium coding problem on strings and stack, asked in Amazon, Google and Microsoft interviews.

You are given a string s of lowercase letters and balanced parentheses.

Reverse the substrings inside each pair of matching parentheses, starting from the innermost pair, and return the result with all brackets removed.

Example 1

Input
s = "(abcd)"
Output
dcba

Example 2

Input
s = "(u(love)i)"
Output
iloveu
Explanation
"love" is reversed first, then the whole thing.

Example 3

Input
s = "(ed(et(oc))el)"
Output
leetcode

Constraints

  • 1 <= s.length <= 40
  • s consists of lowercase English letters and balanced parentheses.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var reverseParentheses = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Reverse Substrings Between Each Pair of Parentheses Solution

Reverse Substrings Between Each Pair of Parentheses solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Reverse Substrings Between Each Pair of Parentheses is a medium coding problem on strings and stack, asked in Amazon, Google and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Strings, Stack
  • Asked at: Amazon, Google, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a string s of lowercase letters and balanced parentheses.

Reverse the substrings inside each pair of matching parentheses, starting from the innermost pair, and return the result with all brackets removed.

Example 1

Input: s = "(abcd)"
Output: dcba

Example 2

Input: s = "(u(love)i)"
Output: iloveu
Explanation: "love" is reversed first, then the whole thing.

Example 3

Input: s = "(ed(et(oc))el)"
Output: leetcode

Constraints

  • 1 <= s.length <= 40
  • s consists of lowercase English letters and balanced parentheses.

Hints for Reverse Substrings Between Each Pair of Parentheses

  1. Hint 1

    Keep a stack of character buffers, one per open bracket level.

  2. Hint 2

    ( starts a new buffer; ) reverses the top buffer and appends it to the one below.

  3. Hint 3

    Everything else is appended to the current buffer, so the innermost pairs resolve first automatically.

How to solve Reverse Substrings Between Each Pair of Parentheses

Keep a stack of character buffers, one per bracket level; ( opens a new buffer, ) reverses the top buffer and appends it to the one below.

Approach

  1. Start with one empty buffer.
  2. On (, push a new buffer; on ), pop, reverse, and extend the new top; otherwise append the letter.
  3. Join the base buffer.

Why it works

Innermost pairs close first, so their contents are reversed before being reversed again by an enclosing pair — exactly the specified semantics.

Complexity

  • Time — O(n²) worst case, O(n) typical
  • Space — O(n)

Pitfalls

  • The linear trick precomputes matching brackets and walks the string flipping direction at each bracket.

Reference solution

Python

def reverseParentheses(s: str) -> str:
    stack = [[]]
    for ch in s:
        if ch == "(":
            stack.append([])
        elif ch == ")":
            inner = stack.pop()
            inner.reverse()
            stack[-1].extend(inner)
        else:
            stack[-1].append(ch)
    return "".join(stack[0])

Java

public static String reverseParentheses(String s) {
    StringBuilder out = new StringBuilder();
    Deque<Integer> starts = new ArrayDeque<>();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(') {
            starts.push(out.length());
        } else if (c == ')') {
            int st = starts.pop();
            int a = st, b = out.length() - 1;
            while (a < b) {
                char t = out.charAt(a);
                out.setCharAt(a, out.charAt(b));
                out.setCharAt(b, t);
                a++;
                b--;
            }
        } else {
            out.append(c);
        }
    }
    return out.toString();
}

C++

string reverseParentheses(string s) {
    string out;
    vector<int> starts;
    for (char c : s) {
        if (c == '(') {
            starts.push_back((int) out.size());
        } else if (c == ')') {
            int st = starts.back();
            starts.pop_back();
            reverse(out.begin() + st, out.end());
        } else {
            out.push_back(c);
        }
    }
    return out;
}

JavaScript

var reverseParentheses = function(s) {
    const stack = [[]];
    for (let i = 0; i < s.length; i++) {
        const c = s.charAt(i);
        if (c === "(") {
            stack.push([]);
        } else if (c === ")") {
            const inner = stack.pop();
            inner.reverse();
            const top = stack[stack.length - 1];
            for (let j = 0; j < inner.length; j++) top.push(inner[j]);
        } else {
            stack[stack.length - 1].push(c);
        }
    }
    return stack[0].join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Stack Data Structure