Problem statement

https://binarysearch.com/problems/Removing-Enclosed-Parentheses/

Solution

The idea if for each open bracket find where it ends, using stack. Then start with 0, 1,... and check if corresponding brackets is n - 1, n - 2, ....

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[last] = i
            return d

        d, n, i = corr(s), len(s), 0
        while i in d and d[i] == n - 1 - i:
            i += 1
        return s[i:-i] if i else s