Reverse Substrings Between Each Pair of Parentheses

Reverse Substrings Between Each Pair of Parentheses - Problem

String Stack Medium

You are given a string s that consists of lowercase 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.

Input & Output

Example 1 — Nested Parentheses

$ Input: s = "(u(love)i)"

› Output: iloveu

💡 Note: First reverse innermost "love" → "evol", giving "(uevoli)". Then reverse "uevoli" → "iloveu" and remove brackets.

Example 2 — Multiple Groups

$ Input: s = "(ed(et(oc))el)"

› Output: leetcode

💡 Note: Process innermost: "oc" → "co", then "etco" → "octe", then "edocteel" → "leetcode".

Example 3 — No Parentheses

$ Input: s = "abcd"

› Output: abcd

💡 Note: No parentheses to process, return string as-is.

Constraints

1 ≤ s.length ≤ 2000
s only contains lowercase English letters and parentheses
It is guaranteed that all parentheses are balanced

Visualization

Tap to expand

Understanding the Visualization

Input

String with nested parentheses: "(u(love)i)"

Process Innermost

Reverse "love" → "evol", giving "(uevoli)"

Process Outer

Reverse "uevoli" → "iloveu", remove brackets

Key Takeaway

🎯 Key Insight: Use stack to handle nested structure naturally - each parentheses level becomes a stack frame

Asked in

a Amazon 25 G Google 18 M Microsoft 12 f Facebook 8

The key insight is that nested parentheses create a natural stack structure. The stack approach is most intuitive: push new levels for '(', reverse and merge on ')'. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Approach	O(n)	O(n)	Use stack to build strings level by level, reversing when closing brackets are found
Wormhole Technique	O(n)	O(n)	Smart traversal that eliminates actual string reversal by using directional navigation
Brute Force - Iterative Replacement	O(n²)	O(n)	Repeatedly find innermost parentheses and reverse their contents

Stack-Based Approach — Algorithm Steps

Step 1: Initialize stack with empty string
Step 2: For each character, if '(' push new empty string to stack
Step 3: If ')', pop current string, reverse it, append to previous level
Step 4: If letter, append to current top of stack
Step 5: Return the final string at bottom of stack

Visualization

Tap to expand

Step-by-Step Walkthrough

Push Levels

Each '(' creates new stack level

Build Strings

Characters added to current level

Pop & Reverse

')' triggers reverse and merge to previous level

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void reverseString(char* str) {
    int len = strlen(str);
    for (int i = 0; i < len / 2; i++) {
        char temp = str[i];
        str[i] = str[len - 1 - i];
        str[len - 1 - i] = temp;
    }
}

char* solution(char* s) {
    int len = strlen(s);
    char** stack = malloc(len * sizeof(char*));
    int stackSize = 0;
    
    // Initialize first level
    stack[stackSize] = malloc((len + 1) * sizeof(char));
    stack[stackSize][0] = '\0';
    stackSize++;
    
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(') {
            // Push new level
            stack[stackSize] = malloc((len + 1) * sizeof(char));
            stack[stackSize][0] = '\0';
            stackSize++;
        } else if (s[i] == ')') {
            // Pop current string, reverse it, append to previous level
            stackSize--;
            char* current = stack[stackSize];
            reverseString(current);
            strcat(stack[stackSize - 1], current);
            free(current);
        } else {
            // Add character to current string
            int currentLen = strlen(stack[stackSize - 1]);
            stack[stackSize - 1][currentLen] = s[i];
            stack[stackSize - 1][currentLen + 1] = '\0';
        }
    }
    
    char* result = malloc((len + 1) * sizeof(char));
    strcpy(result, stack[0]);
    free(stack[0]);
    free(stack);
    
    return result;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string, each character processed once

✓ Linear Growth

Space Complexity

O(n)

Stack stores strings for each nesting level, up to O(n) space

⚡ Linearithmic Space

125.0K Views

Medium Frequency

~15 min Avg. Time

2.5K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler