Problem of The Day: Reverse Substrings Between Each Pair of Parentheses

Problem Statement

Intuition

The problem requires reversing substrings within each pair of parentheses in a given string. A stack can be effectively used to handle the nested structure of parentheses.

Approach

1. Use a stack to keep track of characters.
2. Iterate through the string character by character.
3. If a closing parenthesis is encountered, pop characters from the stack until an opening parenthesis is found, and reverse the popped characters.
4. Push the reversed characters back onto the stack.
5. Continue this process until the end of the string.
6. Finally, join the characters in the stack to form the resultant string.

Complexity

• Time complexity: \(O(n)\), where \(n\) is the length of the string. Each character is pushed and popped from the stack at most once.

• Space complexity: \(O(n)\), where \(n\) is the length of the string, due to the space used by the stack.

Code

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

Editorial

Approach 1: Brute Force

class Solution:
    def reverseParentheses(self, s: str) -> str:
        open_parentheses_indices = deque()
        result = []

        for current_char in s:
            if current_char == "(":
                # Store the current length as the start index
                # for future reversal
                open_parentheses_indices.append(len(result))
            elif current_char == ")":
                start = open_parentheses_indices.pop()
                # Reverse the substring between the matching parentheses
                result[start:] = result[start:][::-1]
            else:
                # Append non-parenthesis characters to the processed list
                result.append(current_char)
        return "".join(result)

• time: O(n^2)
• space: O(n)

Approach 2: Wormhole Teleportation technique

class Solution:
    def reverseParentheses(self, s: str) -> str:
        n = len(s)
        open_parentheses_indices = []
        pair = [0] * n

        # First pass: Pair up parentheses
        for i in range(n):
            if s[i] == "(":
                open_parentheses_indices.append(i)
            if s[i] == ")":
                j = open_parentheses_indices.pop()
                pair[i] = j
                pair[j] = i

        # Second pass: Build the result string
        result = []
        curr_index = 0
        direction = 1

        while curr_index < n:
            if s[curr_index] == "(" or s[curr_index] == ")":
                curr_index = pair[curr_index]
                direction = -direction
            else:
                result.append(s[curr_index])
            curr_index += direction

        return "".join(result)

• time: O(n)
• space: O(n)