Problem statement

https://binarysearch.com/problems/Length-of-Longest-Balanced-Subsequence/

Solution

Equal to Leetcode 1249. Minimum Remove to Make Valid Parentheses.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        def clean(s, op, cl):
            balance, ans = 0, []
            for i in s:
                if i == op:
                    balance += 1
                    ans += i
                elif i == cl and balance > 0:
                    balance -= 1
                    ans += [i]             
            return ans
        
        return len(clean(clean(s, "(", ")")[::-1], ")", "(")[::-1])