Reverse Substrings Between Each Pair of Parentheses
Medium · Stack & Strings · String · Stack
Problem
You are given a string s of lowercase letters and balanced parentheses. For each matching pair of parentheses, reverse the text between them, working from the innermost pair outward.
Return the final string with all parentheses removed.
Examples
Input: s = "(ab(cd))" Output: "cdba"
The inner pair turns cd into dc, giving abdc, which the outer pair reverses to cdba.
Input: s = "x(yz)w" Output: "xzyw"
Only yz is reversed.
Input: s = "(ab(cd(ef))gh)" Output: "hgcdfeba"
(ef) gives fe; cdfe reversed gives efdc; abefdcgh reversed gives hgcdfeba.
Constraints
- 1 <= len(s) <= 2000
- s contains only lowercase English letters and parentheses
- All parentheses in s are balanced
Approaches
- Stack of buffers, reverse at each close — time O(n · d), up to O(n²), space O(n)
Follow-up
Why does jumping work? Text inside k pairs is reversed k times, so it ends up forwards when k is even and backwards when k is odd. Each jump to a partner flips the reading direction exactly once per pair you enter or leave, which is the same parity, so one pass writes the final string with no reversal at all.
Related problems
Start free on Cariara · Coding problems · System design studio
