Problem statement

https://leetcode.com/problems/reverse-substrings-between-each-pair-of-parentheses/

Solution

The idea is to:

  1. Create correspondence of open and closed brackets.
  2. Then we can traverse our string, using jumps: when we meet ( or ), we go to the corresponding bracket, move one step in direction dr and change direction.

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)