分数: 1200 点
问题陈述
给你两个字符串 S 和 T 长度 N 组成 A 和 B。让 s_i 表示 i- 第一个字符 S.
您可以对 S 任意次数,可能为零:
- 选择一个整数对 (i, j) 满足以下条件:
- 1 \leq i < j \leq N
- s_i = s_j =
A - s_{i+1} = s_{i+2} = \ldots = s_{j-1} =
B
- 然后,同时替换每个 s_i, s_{i+1}, \ldots, s_j 与另一个字符 (
A变为B,和B变为A).
确定进行操作所需的最少操作数 S 等于 T。如果不可能,则打印 -1.
约束
- 1 \leq N \leq 2 \times 10^5
- S 和 T 是长度的字符串 N 组成
A和B.
输入
输入由标准输入按以下格式给出:
N S T
输出
如果可以的话 S 等于 T,打印所需的最少操作次数;否则,输出 -1.
示例输入 1
5 AAABA BAAAB
示例输出 1
2
你可以 S 等于 T 分两次操作如下:
- 执行操作 (i, j) = (2, 3). S 变为
ABBBA. - 执行操作 (i, j) = (1, 5). S 变为
BAAAB.
不可能使 S 等于 T 少于两次操作,所以答案是 2.
示例输入 2
1 A B
示例输出 2
-1
不可能使 S 等于 T。请注意,您必须选择 (i, j) 与 i < j.
示例输入 3
1 A A
示例输出 3
0
无需任何操作, S 已经等于 T.
示例输入 4
10 AAABBABAAB BBABBAAABB
示例输出 4
7