Problem statement

https://binarysearch.com/problems/Maximum-Removal-Subsequence-String/

Solution

Let us apply algorithm where we checked that t is subsequence of s, but now we keep places as well. For example if s = xaababcbac and t = abac, we have places 1, 3, 4, 6. Do the same logic from the end - for reversed strings: here it will be 0, 1, 2, 5, after normalization it is 9, 8, 7, 4. Then Imagine that we take 1 element from start and 3 from end, then we have 1 index where prefix ends and 8 index where suffix starts, so gap is 6. We do it for all pairs.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s, t):
        def isSubsequence(s, t):
            si, ti, ans = 0, 0, []
            
            while si < len(s) and ti < len(t):
                if s[si] == t[ti]:
                    ans += [ti]
                si, ti = si + (s[si] == t[ti]), ti + 1
            return ans

        n = len(s)
        a1 = isSubsequence(t, s) 
        a2 = isSubsequence(t[::-1], s[::-1])
        ans = n - 1 - min(a1[-1], a2[-1])
        for x, y in zip(a1, a2[::-1][1:]):
            ans = max(ans, n - 2 - y - x)

        return ans