题解

思路

操作不会改变各字母的出现次数，因此若 $S,T$ 的字符频次不同，答案为 $-1$。

做法

假设进行了 $k$ 次操作，原串前 $k$ 个字符都曾被移走，而后缀 $S_{k+1..N}$ 从未成为首字符，其中各字符的相对顺序不会改变，所以这个后缀必须是 $T$ 的子序列。反过来，只要该后缀是 $T$ 的子序列，保留这些字符的位置后，频次相同保证被移走的前缀字符恰好能够依次插入剩余位置，因而条件也充分。

于是只需求 $S$ 的最长后缀，使它是 $T$ 的子序列。令指针从 $S,T$ 的末尾开始，倒序扫描 $T$；遇到与当前 $S$ 指针相同的字符就把 $S$ 指针左移。扫描结束后，$S$ 中尚未匹配的字符数就是最少操作次数。

复杂度

时间复杂度为 $O(N)$，额外空间复杂度为 $O(1)$。