minimum-operations-to-make-a-subsequence

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

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,3,1,2]</code>. Note that you can insert the integer at the very beginning or end of the array.

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

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&#39; relative order. For example, <code>[2,7,4]</code> is a subsequence of <code>[4,2,3,7,2,1,4]</code> (the underlined elements), while <code>[2,4,2]</code> is not.

&nbsp;
Example 1:

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

Example 2:

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

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= target.length, arr.length &lt;= 105</code></li>
	<li><code>1 &lt;= target[i], arr[i] &lt;= 109</code></li>
	<li><code>target</code> contains no duplicates.</li>
</ul>

minOperations

Minimum Operations to Make a Subsequence

Append Characters to String to Make Subsequence

append-characters-to-string-to-make-subsequence

追加字符以获得子序列

Greedy

Array

Hash Table

Binary Search

给你一个数组 <code>target</code> ，包含若干 互不相同 的整数，以及另一个整数数组 <code>arr</code> ，<code>arr</code> 可能 包含重复元素。

每一次操作中，你可以在 <code>arr</code> 的任意位置插入任一整数。比方说，如果 <code>arr = [1,4,1,2]</code> ，那么你可以在中间添加 <code>3</code> 得到 <code>[1,4,3,1,2]</code> 。你可以在数组最开始或最后面添加整数。

请你返回 最少 操作次数，使得 <code>target</code> 成为 <code>arr</code> 的一个子序列。

一个数组的 子序列 指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。比方说，<code>[2,7,4]</code> 是 <code>[4,2,3,7,2,1,4]</code> 的子序列（加粗元素），但 <code>[2,4,2]</code> 不是子序列。

 

示例 1：

<pre>输入：target = [5,1,3], <code>arr</code> = [9,4,2,3,4]
输出：2
解释：你可以添加 5 和 1 ，使得 arr 变为 [5,9,4,1,2,3,4] ，target 为 arr 的子序列。
</pre>

示例 2：

<pre>输入：target = [6,4,8,1,3,2], <code>arr</code> = [4,7,6,2,3,8,6,1]
输出：3
</pre>

 

提示：

<ul>
	<li><code>1 &lt;= target.length, arr.length &lt;= 105</code></li>
	<li><code>1 &lt;= target[i], arr[i] &lt;= 109</code></li>
	<li><code>target</code> 不包含任何重复元素。</li>
</ul>