分数: 400 点
问题陈述
给你字符串 S 和 T 长度 N 由小写英文字母组成。
您可以重复以下操作任意次数(可能为零)。
- 删除 第一 的性格 S 并在任意位置插入相同的字符 S.
判断是否可以使 S 等于 T,如果可能的话,找到所需的最少操作数。
约束
- 1 \le N \le 2 \times 10^5
- S 和 T 是长度的字符串 N 由小写英文字母组成。
输入
输入由标准输入按以下格式给出:
N S T
输出
如果不可能 S 等于 T,打印 -1。如果可能,请打印所需的最少操作数。
示例输入 1
4 abab abba
示例输出 1
2
你可以 S 等于 T 分两次操作,如下。
- 删除第一个字符 S,然后插入该字符
a结束时 S,制作 Sbaba. - 删除第一个字符 S,然后插入该字符
b之间 2-nd 和 3-rd 字符 S,制作 Sabba.
不可能使 S 等于 T 一次或更少的操作,所以答案是 2.
示例输入 2
3 arc cra
示例输出 2
2