1190. Reverse Substrings Between Each Pair of Parentheses

MediumStackString

Problem Description

In this problem, you are given a string s which is a sequence of lower case English letters and parentheses (brackets). Your task is to process the string by reversing the substrings within each pair of matching parentheses. Importantly, you need to begin this process with the innermost pair of brackets and work your way outwards. The expected output is a string that has no parentheses and reflects the reversals that happened within each (formerly) enclosed section.

Intuition

To solve this problem, we need to simulate the process of reversing characters within the parentheses. We could approach this problem iteratively or recursively, but regardless of the approach, the challenge is to manage the parentheses and the elements between them efficiently.

Intuitively, we can think of each pair of parentheses as a signal to reverse the string within them. When we encounter an opening parenthesis, it indicates the start of a section that will eventually be reversed. A closing parenthesis signals the end of such a section. Since we want to start with the innermost pair, we can't just reverse as we go because they could be nested. We must find a way to pair opening and closing parentheses and then reverse the substrings when we know we've reached the innermost pair.

To achieve this, we use a stack to keep track of the indices of the opening parentheses. When we encounter a closing parenthesis, we pop the last index from the stack which corresponds to the matching opening parenthesis. By marking the positions with indices, we can then navigate back and forth in the string.

The code uses a stack and an additional array, d, to store the indices of where to "jump" next when a parenthesis is encountered. When processing the string, if we hit a closing parenthesis, we use the associated opening index to jump back to the opening parenthesis. The x variable changes the direction of traversal each time we encounter a parenthesis. This allows us to traverse the string outwards from the innermost nested parentheses.

The solution is very clever because it linearizes the steps needed to reverse the substrings. If you picture the parenthesis matching, it's like unfolding the string by making connections between each pair; you hop from one parenthesis to its partner, and back, but each time you ignore the pair you just left, effectively collapsing the string's nested structure.

At the end of this process, the string is traversed, taking into account all reversals, and we join together all non-parenthesis characters to form the result.

Learn more about Stack patterns.

Solution Approach

The solution approach is centered around identifying and processing the nested structures within the input string, s. The key algorithmic technique used in this implementation is a stack, which is a last-in-first-out (LIFO) data structure. The stack is utilized to keep track of opening parentheses indices.

Here is a step-by-step explanation of how the algorithm executes:

Initialize a stack, stk, to store indices of opening parentheses.
Initialize an array, d, of the same length as the input string, s. This array will be used to track the jump positions after we encounter a parenthesis.
Iterate through each character in the string s by its index i:
- If the current character is an opening parenthesis '(', push its index onto the stack.
- If it's a closing parenthesis ')', pop an index from the stack (this represents the matching opening parenthesis), and update the d array at both the opening and closing parentheses' positions, setting them to point at each other (i.e., d[i] and d[j] are set to j and i respectively to create a 'jump' from one parenthesis to the matching one).
After setting up the 'jumps' with the d array, we initialize two variables, i with the value of 0 (to start at the beginning of the string) and x with the value of 1 (to move forward initially).
Create an empty list ans to store the characters of the final result.
While i is within the bounds of the string length:
- If s[i] is a parenthesis, use the d array at index i to jump to the matching parenthesis, and reverse the traversal direction by negating x (x = -x).
- Otherwise, append the current character s[i] to the ans list.
- Move to the next character by updating i (i += x), with x managing the direction of traversal.
After completing the traversal, return the result by joining all elements in ans to form the final string without any brackets.

This method allows the program to "skip" over the parts of the string that have been processed and dynamically reverse the direction of traversal when it moves between matching parentheses. The stack ensures that we always find the innermost pair of parentheses first, and the d array allows us to traverse the string efficiently without recursion and without modifying the input string.

By using this stack and jump array technique, we intelligently collapse nested structures, mimicking the effect of recursive reversal, and ultimately, we achieve a linear-time solution with respect to the input size.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach with the input string s = "(ed(et(oc))el)". We want to reverse the substrings within each pair of parentheses, starting from the innermost one.

Here is how the algorithm would execute on this example:

Initialize an empty stack stk and an array d of the same length as s. In our case, s has a length of 13, so d would be an array of 13 uninitialized elements.
Iterate over each character in s.
- At index 0, we encounter '(', so we push 0 onto the stack.
- At index 1, the character is 'e', and we do nothing.
- At index 2, the character is 'd', and we do nothing.
- At index 3, we encounter '(', so we push 3 onto the stack.
- At index 4, the character is 'e', and we do nothing.
- At index 5, we encounter 't', and we do nothing.
- At index 6, the character is '(', so we push 6 onto the stack.
- At index 7, we encounter 'o', and again, we do nothing.
- At index 8, we encounter 'c', and we do nothing.
- At index 9, we encounter the closing parenthesis ')'. We pop 6 from the stack, which is the index of the matching opening parenthesis. In d, we set d[6] to 9 and d[9] to 6 to create a 'jump' between these indices.
- At index 10, we encounter ')', so we pop 3 from the stack and in d set d[3] to 10 and d[10] to 3.
- At index 11, we encounter another ')', so we pop 0 from the stack and in d set d[0] to 11 and d[11] to 0.
- At index 12, we have 'l', and we do nothing.
Now we start traversing the string with i = 0 and x = 1.
- We skip the parenthesis at s[0] by jumping to s[d[0]], which is s[11] and change the direction of x to -1.
- We continue to traverse backward, appending 'l', 'e', skipping s[10] by jumping to s[d[10]] which is s[3], append 'e', 't', skipping s[6] by jumping to s[d[6]] which is s[9], append 'c', 'o', then move backward from s[6] since our direction is still -1 and append 't', 'e'.
- Eventually, we hit s[0] again, and we reverse the direction to forward (x = 1) and continue appending to ans from s[1] onwards.
After i has traversed all characters, the list ans consists of the characters: ['l', 'e', 'e', 't', 'c', 'o', 'd', 'e'].
Finally, we join all elements in ans to form the final string 'leetcode', which is returned as the result.

The given example successfully demonstrates the clever use of a stack to track the opening parentheses and a jump array to manage traversal effectively, allowing us to unfold and reverse nested string structures efficiently.

Solution Implementation

1class Solution:
2    def reverseParentheses(self, s: str) -> str:
3        length_of_string = len(s)
4        # Create a mapping array of the same length as the input string
5        mapping = [0] * length_of_string
6        # Stack to hold the indexes of the opening parentheses
7        stack = []
8      
9        # For each character in the string with its index
10        for index, character in enumerate(s):
11            if character == '(':
12                # If it's an opening bracket, append its index to stack
13                stack.append(index)
14            elif character == ')':
15                # If it's a closing bracket, pop the last opening bracket's index
16                opening_index = stack.pop()
17                # Update the mapping array where the closing bracket points to the opening bracket and vice versa
18                mapping[index], mapping[opening_index] = opening_index, index
19              
20        # Initialize pointers and direction
21        index = 0
22        direction = 1
23        # List to accumulate the characters of the final answer
24        result = []
25        # Iterate over the input string
26        while index < length_of_string:
27            if s[index] in '()':
28                # If the current character is a parenthesis,
29                # flip the direction and jump to the corresponding parenthesis
30                index = mapping[index]
31                direction = -direction
32            else:
33                # Else, append the current character to the result
34                result.append(s[index])
35            # Move to the next character considering the current direction
36            index += direction
37          
38        # Combine the characters in the result to form the final string
39        return ''.join(result)
40

1class Solution {
2    public String reverseParentheses(String s) {
3        int length = s.length(); // Length of the input string.
4        int[] pairIndex = new int[length]; // Array to keep track of the indices of matching parentheses.
5        Deque<Integer> stack = new ArrayDeque<>(); // Stack to hold the indices of the '(' characters.
6
7        // First pass: Find pairs of parentheses and record their indices.
8        for (int i = 0; i < length; ++i) {
9            if (s.charAt(i) == '(') {
10                // When we encounter an opening parenthesis, we push its index onto the stack.
11                stack.push(i);
12            } else if (s.charAt(i) == ')') {
13                // When we encounter a closing parenthesis, we pop the index of the corresponding
14                // opening parenthesis from the stack and record the pairing in the pairIndex array.
15                int j = stack.pop();
16                pairIndex[i] = j;
17                pairIndex[j] = i;
18            }
19        }
20
21        StringBuilder result = new StringBuilder(); // StringBuilder to construct the resulting string.
22        int index = 0; // Current index in the input string.
23        int direction = 1; // Direction of iteration: 1 for forward, -1 for backward.
24
25        // Second pass: Construct the result using the paired indices to reverse substrings as needed.
26        while (index < length) {
27            if (s.charAt(index) == '(' || s.charAt(index) == ')') {
28                // If the current character is a parenthesis, we switch direction and jump to its pair.
29                index = pairIndex[index];
30                direction = -direction;
31            } else {
32                // Otherwise, we append the current character to the result.
33                result.append(s.charAt(index));
34            }
35            index += direction; // Move to the next character in the current direction.
36        }
37
38        return result.toString(); // Convert the StringBuilder to a String and return it.
39    }
40}
41

1#include <stack>
2#include <vector>
3#include <string>
4
5class Solution {
6public:
7    // Function for reversing substrings within parentheses.
8    std::string reverseParentheses(std::string s) {
9        int length = s.size(); // Length of the input string.
10        std::vector<int> pairedIndex(length); // This vector holds paired indices of parentheses.
11        std::stack<int> openParensStack; // Stack to keep track of the positions of '('.
12
13        // First pass: identify and record positions of paired parentheses
14        for (int i = 0; i < length; ++i) {
15            if (s[i] == '(') {
16                // When we encounter '(', push the index on the stack.
17                openParensStack.push(i);
18            } else if (s[i] == ')') {
19                // For ')', pop the top of the stack to find the matching '('.
20                int matchedIndex = openParensStack.top();
21                openParensStack.pop();
22                pairedIndex[i] = matchedIndex; // Set the pair for ')'.
23                pairedIndex[matchedIndex] = i; // Set the pair for '('.
24            }
25        }
26
27        std::string result; // This will hold the final output string.
28        int index = 0; // Current index in the string.
29        int direction = 1; // Direction of traversal. 1 for forward, -1 for backward.
30
31        // Second pass: build the result string by navigating through the pairs.
32        while (index < length) {
33            if (s[index] == '(' || s[index] == ')') {
34                // On hitting a parenthesis, jump to its pair and invert direction
35                index = pairedIndex[index];
36                direction = -direction;
37            } else {
38                // Otherwise, just add the current character to the result
39                result.push_back(s[index]);
40            }
41            index += direction; // Move in the current direction.
42        }
43
44        return result; // Return the final reversed string.
45    }
46};
47

1/**
2 * Takes a string s, reverses the substrings that are within each pair of parentheses, 
3 * and returns a single string as a result.
4 * @param {string} s - The input string containing parentheses and other characters
5 * @return {string} - The string with the parentheses' contents reversed
6 */
7function reverseParentheses(s: string): string {
8    // Length of the input string
9    const length: number = s.length;
10    // Array to keep track of mirror indices of parentheses
11    const mirror: number[] = new Array(length).fill(0);
12    // Stack to keep indices of opening parentheses
13    const stack: number[] = [];
14
15    // Loop through the string to find and record mirror indices
16    for (let i = 0; i < length; ++i) {
17        if (s[i] === '(') {
18            // Push the index of the opening parenthesis onto the stack
19            stack.push(i);
20        } else if (s[i] === ')') {
21            // Pop the stack to get the matching opening parenthesis index
22            const j = stack.pop() as number; // as number is safe here, because stack is guaranteed to be non-empty
23            // Record the mirror index for both parentheses
24            mirror[i] = j;
25            mirror[j] = i;
26        }
27    }
28
29    // Initialize the index and step variables for traversing the string
30    let index: number = 0;
31    let step: number = 1;
32    // Initialize the result array to construct the reversed string
33    const result: string[] = [];
34
35    // Traverse the string to construct the result while handling parentheses
36    while (index < length) {
37        const char: string = s.charAt(index);
38        if (char === '(' || char === ')') {
39            // Jump to mirror index and reverse traversal direction upon encountering a parenthesis
40            index = mirror[index];
41            step = -step;
42        } else {
43            // Otherwise, add the current character to the result array
44            result.push(char);
45        }
46        // Move to the next character in the specified direction
47        index += step;
48    }
49
50    // Return the reconstructed string without parentheses
51    return result.join('');
52}
53

Time and Space Complexity

The time complexity of the given code can be analyzed as follows:

Iterating over the string s to populate the d array and handling the stack operations takes O(n) time, where n is the length of the string. This is because each character in the string is visited once.
The second while loop also takes O(n) time as it iterates over each character of the string and performs constant time operations (unless i is set to a previously visited index, but due to the nature of the problem this cannot lead to an overall time complexity worse than O(n)).

Thus, the total time complexity of the algorithm is O(n).

The space complexity of the given code can be analyzed as follows:

The d array takes O(n) space to store the indices that should be jumped to when a parenthesis is encountered.
The stack stk takes at most O(n/2) space in the case where half of the string consists of '(' characters before any ')' character is encountered. However, O(n/2) simplifies to O(n).
The list ans also grows to hold O(n) characters, as it holds the result string with parentheses characters removed.

Therefore, the total space complexity of the algorithm is O(n) (since O(n) + O(n) still simplifies to O(n)).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don’t know