1713. The minimum number of operations to obtain a subsequence

This is the 7th day of my participation in the August More Text Challenge

You are given an array target, which contains several different integers, and another array of integers, arr, which may contain duplicate elements.

In each operation, you can insert any integer anywhere in the ARR. For example, if arr = [1,4,1,2], then you can add 3 in the middle to get [1,4,3,1,2]. You can add integers at the beginning or the end of the array.

Return the minimum number of operations to make target a subsequence of ARR.

A subsequence of an array is an array that removes some elements (perhaps none) of the original array without changing the relative order of the rest of the elements. For example, [2,7,4] is a subsequence (bold element) of [4,2,3,7,2,1,4], but [2,4,2] is not a subsequence.

Example 1:

Input: target = [5,1,3], arr = [9,4,2,3,4] output: 2 explanation: you can add 5 and 1 so that arr becomes [5,9,4,1,2,3,4] and target is a subsequence of arr. Example 2:

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

Their thinking

Because the array target contains several different integers, we can use map to map the array elements to their subscripts
When iterating through the arR array, we can use the map to find the subscript of the element at target. Since we need to add the minimum number of elements to make target a subsequence of ARR, our goal is to select the longest subsequence in the target array (which is also a subsequence of ARR). So you can end up with the problem of the longest increasing subsequence, mapping the ARR array to the subscript array of target

code

func minOperations(target []int, arr []int) int {

	n := len(target)
	m:= make(map[int]int, n)
	for i, v := range target {
		m[v]=i
	}
	res := []int{}
	for _, v := range arr {
		
		ifi2,has := m[v]; has { searchInts := sort.SearchInts(res, i2)if searchInts<len(res) {
				res[searchInts]=i2
			}else {
				res=append(res,i2)
			}
		}
	}
	return n-len(res)

}
` `** Bold **Copy the code

1713. The minimum number of operations to obtain a subsequence