<p>You are given an array <code>target</code> that consists of <strong>distinct</strong> integers and another integer array <code>arr</code> that <strong>can</strong> have duplicates.</p>

<p>In one operation, you can insert any integer at any position in <code>arr</code>. For example, if <code>arr = [1,4,1,2]</code>, you can add <code>3</code> in the middle and make it <code>[1,4,<u>3</u>,1,2]</code>. Note that you can insert the integer at the very beginning or end of the array.</p>

<p>Return <em>the <strong>minimum</strong> number of operations needed to make </em><code>target</code><em> a <strong>subsequence</strong> of </em><code>arr</code><em>.</em></p>

<p>A <strong>subsequence</strong> of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements&#39; relative order. For example, <code>[2,7,4]</code> is a subsequence of <code>[4,<u>2</u>,3,<u>7</u>,2,1,<u>4</u>]</code> (the underlined elements), while <code>[2,4,2]</code> is not.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> target = [5,1,3], <code>arr</code> = [9,4,2,3,4]
<strong>Output:</strong> 2
<strong>Explanation:</strong> You can add 5 and 1 in such a way that makes <code>arr</code> = [<u>5</u>,9,4,<u>1</u>,2,3,4], then target will be a subsequence of <code>arr</code>.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> target = [6,4,8,1,3,2], <code>arr</code> = [4,7,6,2,3,8,6,1]
<strong>Output:</strong> 3
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= target.length, arr.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= target[i], arr[i] &lt;= 10<sup>9</sup></code></li>
	<li><code>target</code> contains no duplicates.</li>
</ul>


//Approach 1
// class Solution {
// public:
//     int minOperations(vector<int>& target, vector<int>& arr) {

//         int m = target.size();
//         int n = arr.size();

//         vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

//         for (int i = 1; i <= m; i++)
//         {
//             for (int j = 1; j <= n; j++)
//             {
//                 if (target[i-1] == arr[j-1])
//                 {
//                     dp[i][j] = 1 + dp[i-1][j-1];
//                 }
//                 else
//                 {
//                     dp[i][j] = max( dp[i-1][j], dp[i][j-1]);
//                 }
//             }
//         }

//         return m - dp[m][n];
        
//     }
// };

//Approach 2
// class Solution {
//     vector<vector<int>> dp;
// public:
//     int LCS(vector<int>& target, vector<int>& arr, int m , int n)
//     {
//         if (m == 0 || n ==0)
//          return 0;

//         if (dp[m][n] != -1)
//             return dp[m][n];
        
//         if (target[m-1] == arr[n-1])
//         {
//             return dp[m][n] = 1 + LCS(target, arr, m - 1, n - 1);
//         }
//         else
//         {
//             return dp[m][n] = max(LCS(target, arr, m - 1, n), LCS(target, arr, m, n - 1));
//         }
        
        
//     }
//     int minOperations(vector<int>& target, vector<int>& arr) {

//         int m = target.size();
//         int n = arr.size();

//         dp.resize(m + 1, vector<int>(n + 1, -1));

//         int res = LCS(target, arr, m ,n);

       

//         return m - res;
        
//     }
// };

//Approach 3
class Solution {
    
public:
    
    int minOperations(vector<int>& target, vector<int>& arr) {
        unordered_map<int, int> hashmap;
        vector<int> st;
        int m = target.size();
        int n = arr.size();

        for (int i = 0 ; i < m; i++)
        {
            hashmap[target[i]] = i;
        }

        for (int i = 0 ; i < n; i++)
        {
            if (!hashmap.count(arr[i]))
                continue;
            auto it = lower_bound(st.begin(), st.end(), hashmap[arr[i]]);
            if (it == st.end())
             st.push_back(hashmap[arr[i]]);
            else
             *it = hashmap[arr[i]];
        }

        return m - st.size();        
    }
};
113600