Krammer's blog

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

Thinking process:

Classic LIS (longest increasing sequence) problem. For each number in arr, if it’s in the target array, we convert that number into the index in target array, and then process like we’re working on LCS. We replace the current index with the smallest index which is greater than the current index so far. We do this because there is no need to keep tracking the “smallest index which is greater than the current index” because the result will be the same if we only track the current one.

For more detail, check this one https://leetcode.com/problems/longest-increasing-subsequence/.

Here is the code.

 1class Solution {
 2public:
 3    int minOperations(vector<int>& target, vector<int>& arr) {
 4        unordered_map<int, int> mp;
 5        int N = target.size();
 6        for (int i=0; i<N; i++) {
 7            mp[target[i]] = i;
 8        }
 9        vector<int> lcs;
10        for (auto a : arr) {
11            if (mp.count(a)) {
12                auto it = upper_bound(lcs.begin(), lcs.end(), mp[a]);
13                if (it != lcs.begin() and *(it-1) == mp[a]) continue; // de-dupe
14                if (it == lcs.end()) lcs.push_back(mp[a]);
15                else *it = mp[a];
16            }
17        }
18        return N - lcs.size();
19    }
20};

Editorial: LeetCode 1713 Minimum Operations to Make a Subsequence