BinarySearch 0639 Delete From the Ends and Reinsert to Target

Problem statement

https://binarysearch.com/problems/Delete-From-the-Ends-and-Reinsert-to-Target/

Solution

Let us reverse our problem: start with t and then we can take symbol from any place and put it to the start or to the end. After several such operation we will have prefix + midfix + suffix. Notice that elements in midfix will have the same order as in original array. Also we need to minimize sum of length of prefix and suffix, which is equivalent to maximizing the length of midfix. So, finally, what we need to find is the longest substring of t, which is subsequence of s. It is very similar to classical LCS (Longest Common Subsequence) problem, but do not look at dp(i - 1, j) here.

Complexity

It is O(n^2) for time and space.

Code

class Solution:
    def solve(self, s, t):
        @lru_cache(None)
        def dp(i, j):
            return max(dp(i, j-1), (1 + dp(i-1, j-1)) * (s[i-1] == t[j-1])) if i*j else 0
        
        n, m = len(s), len(t)
        return n - max(dp(i, j) for i, j in product(range(n+1), range(m+1)))