subsequence-with-the-minimum-score

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 two strings <code>s</code> and <code>t</code>.

You are allowed to remove any number of characters from the string <code>t</code>.

The score of the string is <code>0</code> if no characters are removed from the string <code>t</code>, otherwise:

<ul>
	<li>Let <code>left</code> be the minimum index among all removed characters.</li>
	<li>Let <code>right</code> be the maximum index among all removed characters.</li>
</ul>

Then the score of the string is <code>right - left + 1</code>.

Return the minimum possible score to make <code>t</code>&nbsp;a subsequence of <code>s</code>.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;abcde&quot;</code> while <code>&quot;aec&quot;</code> is not).

&nbsp;
Example 1:

<pre>
Input: s = &quot;abacaba&quot;, t = &quot;bzaa&quot;
Output: 1
Explanation: In this example, we remove the character &quot;z&quot; at index 1 (0-indexed).
The string t becomes &quot;baa&quot; which is a subsequence of the string &quot;abacaba&quot; and the score is 1 - 1 + 1 = 1.
It can be proven that 1 is the minimum score that we can achieve.
</pre>

Example 2:

<pre>
Input: s = &quot;cde&quot;, t = &quot;xyz&quot;
Output: 3
Explanation: In this example, we remove characters &quot;x&quot;, &quot;y&quot; and &quot;z&quot; at indices 0, 1, and 2 (0-indexed).
The string t becomes &quot;&quot; which is a subsequence of the string &quot;cde&quot; and the score is 2 - 0 + 1 = 3.
It can be proven that 3 is the minimum score that we can achieve.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length, t.length &lt;= 105</code></li>
	<li><code>s</code> and <code>t</code> consist of only lowercase English letters.</li>
</ul>

minimumScore

Subsequence With the Minimum Score

Longest Common Subsequence

longest-common-subsequence

最长公共子序列

Two Pointers

String

Binary Search

给你两个字符串&nbsp;<code>s</code> 和&nbsp;<code>t</code>&nbsp;。

你可以从字符串 <code>t</code>&nbsp;中删除任意数目的字符。

如果没有从字符串&nbsp;<code>t</code>&nbsp;中删除字符，那么得分为&nbsp;<code>0</code>&nbsp;，否则：

<ul>
	<li>令&nbsp;<code>left</code>&nbsp;为删除字符中的最小下标。</li>
	<li>令&nbsp;<code>right</code>&nbsp;为删除字符中的最大下标。</li>
</ul>

字符串的得分为&nbsp;<code>right - left + 1</code>&nbsp;。

请你返回使&nbsp;<code>t</code> 成为&nbsp;<code>s</code>&nbsp;子序列的最小得分。

一个字符串的 子序列&nbsp;是从原字符串中删除一些字符后（也可以一个也不删除），剩余字符不改变顺序得到的字符串。（比方说&nbsp;<code>"ace"</code> 是&nbsp;<code>"abcde"</code>&nbsp;的子序列，但是&nbsp;<code>"aec"</code>&nbsp;不是）。

&nbsp;

示例 1：

<pre>
输入：s = "abacaba", t = "bzaa"
输出：1
解释：这个例子中，我们删除下标 1 处的字符 "z" （下标从 0 开始）。
字符串 t 变为 "baa" ，它是字符串 "abacaba" 的子序列，得分为 1 - 1 + 1 = 1 。
1 是能得到的最小得分。
</pre>

示例 2：

<pre>
输入：s = "cde", t = "xyz"
输出：3
解释：这个例子中，我们将下标为 0， 1 和 2 处的字符 "x" ，"y" 和 "z" 删除（下标从 0 开始）。
字符串变成 "" ，它是字符串 "cde" 的子序列，得分为 2 - 0 + 1 = 3 。
3 是能得到的最小得分。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length, t.length &lt;= 105</code></li>
	<li><code>s</code> 和&nbsp;<code>t</code>&nbsp;都只包含小写英文字母。</li>
</ul>

&nbsp;