Problem statement

https://leetcode.com/problems/minimum-operations-to-make-a-subsequence/

Solution

We can see that we need to find in fact the longest common subsequence between two string. Also we need to use the given information that values in target is different. This problem can be solved with LIS. First of all we need to rename all values in target, so they are increasing. Then we delete all elements from A which are not in target and rename others. Then we just need to find LIS.

Complexity

It is O(n log n) for time and O(n) for space.

Code

from bisect import bisect_left

class Solution:
    def minOperations(self, target, arr):
        d = {x:i for i, x in enumerate(target)}
        A = [d[x] for x in arr if x in d]
       
        dp = [10**10] * (len(A) + 1)
        for elem in A: 
            dp[bisect_left(dp, elem)] = elem  
        
        return len(target) - dp.index(10**10)