1190. Reverse Substrings Between Each Pair of Parentheses

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.

Constraints:

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

Approach 01:

class Solution {
public:
    string reverseParentheses(string s) {
        stack<int> openParenthesisIndices;
        string result;

        for (const char c : s) {
            if (c == '(') {
                openParenthesisIndices.push(result.length());
            } else if (c == ')') {
                // Reverse the corresponding substring between ().
                const int startIndex = openParenthesisIndices.top();
                openParenthesisIndices.pop();
                reverse(result.begin() + startIndex, result.end());
            } else {
                result += c;
            }
        }

        return result;
    }
};

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

        for c in s:
            if c == '(':
                open_parenthesis_indices.append(len(result))
            elif c == ')':
                start_index = open_parenthesis_indices.pop()
                result[start_index:] = reversed(result[start_index:])
            else:
                result.append(c)

        return ''.join(result)

Time Complexity

• Iterating through the string:

  The algorithm iterates through each character of the string s exactly once. This takes \( O(n) \) time, where \( n \) is the length of the string.

• Reversing substrings:

  Each reversal operation is done in place and each character in the string is reversed at most once. Therefore, the total time spent on reversing is also \( O(n) \).

• Overall Time Complexity:

  The overall time complexity is \( O(n) \), where \( n \) is the length of the string.

Space Complexity

• Stack space:

  The stack stores indices of open parentheses. In the worst case, the stack could store \( O(n) \) indices if there are many nested parentheses.

• Result string:

  The result string is built incrementally and, in the worst case, can have the same length as the input string \( s \), resulting in \( O(n) \) space.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \), where \( n \) is the length of the string. This includes space for the stack and the result string.