1190. Reverse Substrings Between Each Pair of Parentheses

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.

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.

Example 4:

Input: s = "a(bcdefghijkl(mno)p)q"
Output: "apmnolkjihgfedcbq"

Constraints:

• 0 <= s.length <= 2000
• s only contains lower case English characters and parentheses.
• It's guaranteed that all parentheses are balanced.

Problem Summary

Given a string s (containing only lowercase English letters and parentheses). Reverse the strings inside each pair of matching parentheses layer by layer, from the inside out, and return the final result. Note that your result should not contain any parentheses.

Solution Ideas

• The most straightforward approach for this problem is to use a stack to push the strings inside each pair of parentheses onto the stack, and when encountering a ")" parenthesis, pop from the stack and reverse it. Since a stack data structure is used, there is no need to worry about multiple levels of nested parentheses. This method of pushing and popping while reversing strings has a time complexity of O(n^2). Is it possible to reduce the time complexity further?
• In the above solution, there is repeated traversal. When scanning the original string, pushing and popping already scans once; when popping at a ")" parenthesis, reversing will scan the already pushed string again. This repeated traversal can be optimized away. In the first loop, mark the reversal intervals first. For example, when encountering "(", push it onto the stack and record its index. When encountering ")", it means this pair of parentheses has been matched, so swap the index of ")" with the index of the previously pushed "(". This traversal marks the reversal intervals. Then traverse once more and reverse the string according to the reversal intervals. Strings not in a reversal interval are appended normally. If inside a reversal interval, traverse in reverse order and add to the final result string. In this way, the time complexity is only O(n). See the code below for the specific implementation.

Code

package leetcode

func reverseParentheses(s string) string {
	pair, stack := make([]int, len(s)), []int{}
	for i, b := range s {
		if b == '(' {
			stack = append(stack, i)
		} else if b == ')' {
			j := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			pair[i], pair[j] = j, i
		}
	}
	res := []byte{}
	for i, step := 0, 1; i < len(s); i += step {
		if s[i] == '(' || s[i] == ')' {
			i = pair[i]
			step = -step
		} else {
			res = append(res, s[i])
		}
	}
	return string(res)
}