Code Implementation

class Solution:
    def reverseParentheses(self, s: str) -> str:
        stack = []
        for ch in s:
            if ch == ')':
                temp = []
                while stack and stack[-1] != '(':
                    temp.append(stack.pop())
                stack.pop()  # Remove the '('
                stack.extend(temp)
            else:
                stack.append(ch)
        return ''.join(stack)
      

class Solution {
public:
    string reverseParentheses(string s) {
        stack<char> stk;
        for (char ch : s) {
            if (ch == ')') {
                string temp;
                while (!stk.empty() && stk.top() != '(') {
                    temp += stk.top();
                    stk.pop();
                }
                stk.pop(); // Remove '('
                for (char c : temp) stk.push(c);
            } else {
                stk.push(ch);
            }
        }
        string result;
        while (!stk.empty()) {
            result += stk.top();
            stk.pop();
        }
        reverse(result.begin(), result.end());
        return result;
    }
};
      

class Solution {
    public String reverseParentheses(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (ch == ')') {
                StringBuilder temp = new StringBuilder();
                while (!stack.isEmpty() && stack.peek() != '(') {
                    temp.append(stack.pop());
                }
                stack.pop(); // Remove '('
                for (char c : temp.toString().toCharArray()) stack.push(c);
            } else {
                stack.push(ch);
            }
        }
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }
        return result.reverse().toString();
    }
}
      

var reverseParentheses = function(s) {
    let stack = [];
    for (let ch of s) {
        if (ch === ')') {
            let temp = [];
            while (stack.length > 0 && stack[stack.length - 1] !== '(') {
                temp.push(stack.pop());
            }
            stack.pop(); // Remove '('
            for (let c of temp) stack.push(c);
        } else {
            stack.push(ch);
        }
    }
    return stack.join('');
};
      

Problem Description

Given a string s containing lowercase English letters and parentheses, you are to reverse the substrings enclosed within each pair of matching parentheses, starting from the innermost pair. The reversed substrings should replace the original ones, and the final result should not contain any parentheses.

For example, if s = "(u(love)i)", the output should be "iloveu".

• Each opening parenthesis '(' has a corresponding closing parenthesis ')'.
• There is one valid way to interpret the parentheses nesting.
• Parentheses are not part of the final output.

Thought Process

The problem involves reversing substrings defined by nested parentheses, starting from the innermost pair. At first glance, one might consider extracting all substrings between parentheses and reversing them recursively. However, this could get complicated with multiple and nested pairs.

A brute-force approach could involve repeatedly finding the innermost pair of parentheses, reversing the substring, and replacing it in the string until no parentheses remain. However, this would require scanning the string multiple times, leading to inefficiency.

To optimize, we can leverage a stack to process the string in a single pass. Each time we encounter a closing parenthesis, we can pop characters from the stack until the matching opening parenthesis is found, reverse the collected substring, and push the reversed characters back onto the stack. This approach naturally handles nesting and ensures we process from the innermost outwards.

Solution Approach

• Use a Stack: We use a stack to store characters as we iterate through the string. The stack allows us to easily access and manipulate the most recently added characters, which is ideal for handling nested structures like parentheses.
• Iterate Through the String: For each character in the string:
  • If the character is not a closing parenthesis ')', push it onto the stack.
  • If the character is a closing parenthesis ')':
    • Pop characters from the stack until an opening parenthesis '(' is encountered. Collect these characters in a temporary list or string.
    • Pop the opening parenthesis '(' from the stack (do not include it in the result).
    • Push the collected characters (which are now reversed due to the order of popping) back onto the stack.
• Build the Final String: After processing the entire string, the stack contains the final result in order. Join the elements to form the output string, excluding any parentheses.
• Why a Stack? The stack structure is perfect for this problem because it allows us to handle nested parentheses by always working with the innermost substring first, which matches the last-in, first-out (LIFO) behavior of stacks.

Example Walkthrough

Let's consider the input s = "(u(love)i)".

1. Process (: push to stack. Stack: [ '(' ]
2. Process u: push to stack. Stack: [ '(', 'u' ]
3. Process (: push to stack. Stack: [ '(', 'u', '(' ]
4. Process l: push to stack. Stack: [ '(', 'u', '(', 'l' ]
5. Process o: push to stack. Stack: [ '(', 'u', '(', 'l', 'o' ]
6. Process v: push to stack. Stack: [ '(', 'u', '(', 'l', 'o', 'v' ]
7. Process e: push to stack. Stack: [ '(', 'u', '(', 'l', 'o', 'v', 'e' ]
8. Process ): pop until '('. We get 'e', 'v', 'o', 'l' (in that order), reverse is "love". Pop '('.
9. Push back 'e', 'v', 'o', 'l' to stack. Stack: [ '(', 'u', 'e', 'v', 'o', 'l' ]
10. Process i: push to stack. Stack: [ '(', 'u', 'e', 'v', 'o', 'l', 'i' ]
11. Process ): pop until '('. We get 'i', 'l', 'o', 'v', 'e', 'u', reverse is "iloveu". Pop '('.
12. Push back 'i', 'l', 'o', 'v', 'e', 'u' to stack. Stack: [ 'i', 'l', 'o', 'v', 'e', 'u' ]
13. Final stack: join to get "iloveu".

This demonstrates how the stack naturally handles the innermost parentheses first, building up the result as we process each closing parenthesis.

Time and Space Complexity

• Brute-force Approach: Repeatedly searching for the innermost parentheses and reversing substrings would require O(n²) time in the worst case, where n is the length of the string, due to repeated scans and substring operations.
• Optimized Stack Approach: Each character is pushed and popped from the stack at most once, resulting in O(n) time complexity.
• Space Complexity: The stack may hold up to all characters in the string, so the space complexity is O(n).

Summary

The key insight is to use a stack to process the string in a single pass, reversing substrings as each closing parenthesis is encountered. This approach elegantly handles nested and multiple parentheses, ensuring efficiency and correctness. The stack structure matches the nesting behavior of the problem, making the solution both intuitive and optimal.