AT_arc154_b [ARC154B] New Place
题目描述
给你两个长度为 $N$ 的字符串 $S$ 和 $T$,仅包含英文小写字母。
你可以重复进行下面的操作(可以不执行):
- 将 $S$ 的第一个字符删去,并将这个字符插入到 $S$ 的任意位置。
问你至少执行多少次操作使得 $S$ 与 $T$ 相等。
输入格式
第一行是一个整数 $N$。第二行是字符串 $S$,第三行是字符串 $T$。
输出格式
如果 $S$ 不可能与 $T$ 相等,输出 `-1`。
否则,输出使 $S$ 和 $T$ 相等所需的最小操作数。
@[hellolin](/user/751017) 译
说明/提示
**约束条件**
- $1 ≤ N ≤ 2 × 10^5$
- $S$ 和 $T$ 是由小写英文字母组成的长度为 $N$ 的字符串
**示例解释 1**
通过如下操作,可以在 $2$ 次内使 $S$ 与 $T$ 一致:
删除 $S$ 的第一个字符,然后将相同的字符 `a` 插入到 $S$ 的末尾。此时 $S$ 变为 `baba`。
删除 $S$ 的第一个字符,然后将相同的字符 `b` 插入到 $S$ 的第 $2$ 个字符与第 $3$ 个字符之间。此时 $S$ 变为 `abba`。
无法在 $1$ 次或更少的操作内使 $S$ 与 $T$ 一致,因此答案为 $2$。