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$。