Problem

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

Examples

Example 1:

Input: s = "(abcd)"
Output: "dcba"

Example 2:

Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.

Example 3:

Input: s = "(ed(et(oc))el)"
Output: "leetcode"
Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.

Solution

Method 1 - Using Stack naively

Let’s tackle the problem step by step:

  1. Use a stack to track the content within parentheses.
  2. As we traverse the string, push characters onto the stack.
  3. When encountering a closing bracket ), pop characters from the stack until an opening bracket ( is found.
  4. Reverse the characters between the brackets and push the reversed content back onto the stack.
  5. Continue until the end of the string.
  6. The remaining characters in the stack form the requested output after removing all brackets.

Code

Java
public class Solution {

	public String reverseParentheses(String s) {
		Stack<Character> stack = new Stack<>();

		for (char ch: s.toCharArray()) {
			if (ch == ')') {
				// Hold characters until the matching '('
				StringBuilder sb = new StringBuilder();

				while (stack.peek() != '(') {
					sb.append(stack.pop());
				}

				stack.pop(); // Remove the '('

				// Reverse the characters and push them back to the stack
				for (char reversedCh: sb.toString().toCharArray()) {
					stack.push(reversedCh);
				}
			} else {
				stack.push(ch);
			}
		}

		// Build the resultant string
		StringBuilder result = new StringBuilder();

		for (char ch: stack) {
			result.append(ch);
		}

		return result.toString();
	}

}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n)

Method 2 - Using stack with pair

In previous solution, we are again and again reversing the part of the string, when we see ) in different parts of the string. Lets look at example, say s = "ab(cd)e(f(gh))i", then lets see impact of nesting on string sections.

So, if you observe carefully, when the string is evenly nested, the string section doesn’t reverses. But if it is oddly nested, the string is reversed, and the order of section in output string depends on the order of nesting.

So, this brings us to jumping on the bracket approach:

  • If we see ( ⇨ we jump to its matching parenthesis ), and direction reverses.
  • add now, we come back to (, then jump to ) but as we have processed this string section, we continue in the direction.

See the updated example below:

But how do we find the matching parenthesis, this is where we use stack, and store the pairs of matching parenthesis.

Approach

We need 2 passes -

  1. In first pass we build the index pairs of matching parenthesis
  2. In second pass, we use these index pairs to form the string
First Pass
  1. Initialize the index pairs pairs[0...n] where n is length of string, storing the indices of matching parenthesis
  2. Now iterate on string characters with index i
    1. When we see ( ⇨ push i stack
    2. When see matching ),
      1. pop out last pushed index; lets call it j
      2. pairs[i] = j and pairs[j] = i
Second Pass
  1. Initialize the string builder sb, direction dir = 1 (1 ⇨ left to right, -1 ⇨ right to left)
  2. Now iterate on string characters with iterator index i
  3. If we see ( or ) we change the direction of iteration and iteration becomes i += dir
  4. Otherwise, we just append character to string

Code

Java
class Solution {

	public String reverseParentheses(String str) {
		int n = str.length();
		Stack<Integer> openIndices = new Stack<>();
		int[] pairs = new int[n];

		for (int i = 0; i < n; ++i) {
			if (str.charAt(i) == '(') {
				openIndices.push(i);
			} else if (str.charAt(i) == ')') {
				int j = openIndices.pop();
				pairs[i] = j;
				pairs[j] = i;
			}
		}

		StringBuilder sb = new StringBuilder();

		for (int i = 0, dir = 1; i < n; i += dir) {
			if (str.charAt(i) == '(' || str.charAt(i) == ')') {
				i = pairs[i];
				dir *= -1;
			} else {
				sb.append(str.charAt(i));
			}
		}

		return sb.toString();
	}

}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)