## 1713. Minimum Operations to Make a Subsequence

You are given an array `target`

that consists of **distinct** integers and another integer array `arr`

that **can** have duplicates.

In one operation, you can insert any integer at any position in `arr`

. For example, if `arr = [1,4,1,2]`

, you can add `3`

in the middle and make it `[1,4,`

. Note that you can insert the integer at the very beginning or end of the array.__3__,1,2]

Return *the minimum number of operations needed to make *

`target`

*a*

**subsequence**of`arr`

*.*

A **subsequence** of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements' relative order. For example, `[2,7,4]`

is a subsequence of `[4,`

(the underlined elements), while __2__,3,__7__,2,1,__4__]`[2,4,2]`

is not.

**Example 1:**

Input:target = [5,1,3],`arr`

= [9,4,2,3,4]Output:2Explanation:You can add 5 and 1 in such a way that makes`arr`

= [5,9,4,1,2,3,4], then target will be a subsequence of`arr`

.

**Example 2:**

Input:target = [6,4,8,1,3,2],`arr`

= [4,7,6,2,3,8,6,1]Output:3

**Constraints:**

`1 <= target.length, arr.length <= 10`

^{5}`1 <= target[i], arr[i] <= 10`

^{9}`target`

contains no duplicates.

## Rust Solution

```
struct Solution;
use std::collections::HashMap;
impl Solution {
fn min_operations(target: Vec<i32>, arr: Vec<i32>) -> i32 {
let n = target.len();
let mut idx: HashMap<i32, usize> = HashMap::new();
for x in target {
idx.insert(x, idx.len());
}
let mut dp = vec![];
for x in arr {
if let Some(&i) = idx.get(&x) {
let j = match dp.binary_search(&i) {
Ok(j) => j,
Err(j) => j,
};
if j < dp.len() {
dp[j] = i;
} else {
dp.push(i);
}
}
}
(n - dp.len()) as i32
}
}
#[test]
fn test() {
let target = vec![5, 1, 3];
let arr = vec![9, 4, 2, 3, 4];
let res = 2;
assert_eq!(Solution::min_operations(target, arr), res);
let target = vec![6, 4, 8, 1, 3, 2];
let arr = vec![4, 7, 6, 2, 3, 8, 6, 1];
let res = 3;
assert_eq!(Solution::min_operations(target, arr), res);
}
```

Having problems with this solution? Click here to submit an issue on github.