Problem statement

https://binarysearch.com/problems/Recursive-Parentheses-Reversal/

Solution

Equal to Leetcode 1190. Reverse Substrings Between Each Pair of Parentheses.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        def corr(s):
            stack, d = [], {}
            for i, elem in enumerate(s):
                if elem == "(":
                    stack.append(i)
                elif elem == ")":
                    last = stack.pop()
                    d[i] = last
                    d[last] = i
            return d

        d, ans, dr, i = corr(s), [], 1, 0

        while len(ans) < len(s) - len(d):
            if s[i] in "()":
                i = d[i] - dr
                dr = -dr
            else:
                ans += [s[i]]
                i += dr

        return "".join(ans)