Reverse Substrings Between Each Pair of Parentheses

Reverse Substrings Between Each Pair of Parentheses

What is this problem about?

The Reverse Substrings Between Each Pair of Parentheses interview question gives you a string containing lowercase letters and nested parentheses. You must reverse the substrings inside each pair of parentheses, starting from the innermost pair and working outward, then return the final string with all parentheses removed. This is a classic stack-based string manipulation problem.

Why is this asked in interviews?

This problem is asked at Agoda, Microsoft, Flipkart, Amazon, Oracle, Google, Bloomberg, and Adobe because it tests systematic use of the stack data structure for handling nested structures. Nested parentheses processing is fundamental to expression parsers, compilers, and document formatting systems. It evaluates whether a candidate can manage state across multiple nesting levels without losing track of context.

Algorithmic pattern used

The primary pattern is stack simulation. Iterate through the string character by character. For non-parenthesis characters, push them onto the stack. When a ( is encountered, push a marker. When ) is encountered, pop characters from the stack until the matching ( marker is found — collect these characters, reverse them, and push them back. At the end, join all characters on the stack to form the result. An O(n) portal-based approach also exists using precomputed pair positions for cleaner traversal without repeated reversals.

Example explanation

Input: "(u(love)i)"

• (: push marker.
• u: push 'u'.
• (: push marker.
• l,o,v,e: push each.
• ): pop until marker → collected 'l','o','v','e' → reversed → 'e','v','o','l' → push back.
• i: push 'i'.
• ): pop until marker → collected 'u','e','v','o','l','i' → reversed → 'i','l','o','v','e','u' → push back.

Stack: ['i','l','o','v','e','u']. Result: "iloveu".

Common mistakes candidates make

• Reversing the entire string instead of only the contents within the innermost unmatched parentheses.
• Forgetting to remove the parenthesis markers from the final result.
• Not handling nested parentheses correctly — the innermost pair must be processed first.
• Using string concatenation inside the loop for each reversal, leading to O(n^2) performance.

Interview preparation tip

For the Reverse Substrings Between Each Pair of Parentheses coding problem, the string and stack interview pattern is the clean approach. Practice the stack-based simulation until it is mechanical. Google and Bloomberg interviewers may ask for the O(n) portal approach — precompute the matching parenthesis index for each ( and ), then traverse using direction flipping instead of explicit reversals. This avoids repeated O(n) reversal steps inside the loop.