1713. Minimum Operations to Make a Subsequence Hard

1/**
2 * [1713] Minimum Operations to Make a Subsequence
3 *
4 * You are given an array target that consists of distinct integers and another integer array arr that can have duplicates.
5 * 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,<u>3</u>,1,2]. Note that you can insert the integer at the very beginning or end of the array.
6 * Return the minimum number of operations needed to make target a subsequence of arr.
7 * 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,<u>2</u>,3,<u>7</u>,2,1,<u>4</u>] (the underlined elements), while [2,4,2] is not.
8 *  
9 * Example 1:
10 * 
11 * Input: target = [5,1,3], arr = [9,4,2,3,4]
12 * Output: 2
13 * Explanation: You can add 5 and 1 in such a way that makes arr = [<u>5</u>,9,4,<u>1</u>,2,3,4], then target will be a subsequence of arr.
14 * 
15 * Example 2:
16 * 
17 * Input: target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
18 * Output: 3
19 * 
20 *  
21 * Constraints:
22 * 
23 * 	1 <= target.length, arr.length <= 10^5
24 * 	1 <= target[i], arr[i] <= 10^9
25 * 	target contains no duplicates.
26 * 
27 */
28pub struct Solution {}
29
30// problem: https://leetcode.com/problems/minimum-operations-to-make-a-subsequence/
31// discuss: https://leetcode.com/problems/minimum-operations-to-make-a-subsequence/discuss/?currentPage=1&orderBy=most_votes&query=
32
33// submission codes start here
34
35impl Solution {
36    pub fn min_operations(target: Vec<i32>, arr: Vec<i32>) -> i32 {
37        0
38    }
39}
40
41// submission codes end
42
43#[cfg(test)]
44mod tests {
45    use super::*;
46
47    #[test]
48    fn test_1713() {
49    }
50}
51