Problem statement

https://binarysearch.com/problems/Maximal-Points-From-Deleting-Two-Character-Substrings/

Solution

I think I saw this problem on leetcode but do not know the number.

Use greedy strategy with two passes and stack: one where we always try to take 01 and then 10. And second pass with different order.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s, x, y):
        def passs(first, second, c1, c2):
            stack, ans = [], 0
            for x in s:
                if x == first and stack and stack[-1] == second:
                    ans += c1
                    stack.pop()
                else:
                    stack += [x]
            return ans + min(stack.count(first), stack.count(second))*c2

        return max(passs("0", "1", y, x), passs("1", "0", x, y))