P8703 [Lanqiao Cup 2019 National B] Optimal Inclusion

We say that a string $S$ contains a string $T$ if $T$ is a subsequence of $S$. That is, we can pick some characters from $S$, and keep their original order to form a new string that is exactly the same as $T$. Given two strings $S$ and $T$, find the minimum number of characters in $S$ that need to be modified so that $S$ contains $T$.

Input consists of two lines, each containing a string. The string on the first line is $S$, and the string on the second line is $T$. Both strings are non-empty and contain only uppercase English letters.

Output one integer, which is the answer.

For $20\%$ of the test cases, $1 \leq |T| \leq |S| \leq 20$. For $40\%$ of the test cases, $1 \leq |T| \leq |S| \leq 100$. For all test cases, $1 \leq |T| \leq |S| \leq 1000$. Lanqiao Cup 2019 National Contest, Group B, Problem F. Translated by ChatGPT 5