分数: 400 点
问题陈述
给你两个字符串 S 和 T 长度 N 组成 A 和 B。让 S_i 表示 i从左边算起第一个字符 S.
您可以重复以下操作任意次数,可能为零:
- 选择整数 i 和 j 这样 1\leq i < j \leq N。更换 S_i 与
A和 S_j 与B.
确定是否可以使 S 等于 T。如果可能的话,找出所需的最少操作次数。
约束
- 2 \leq N \leq 2 \times 10^5
- 每个 S 和 T 是一个长度为 N 组成
A和B. - 所有输入数字均为整数。
输入
输入由标准输入按以下格式给出:
N S T
输出
如果不可能 S 等于 T,打印 -1.
否则,打印执行此操作所需的最少操作数。
示例输入 1
5 BAABA AABAB
示例输出 1
2
执行操作 i=1 和 j=3 变化 S to AABBA.
执行操作 i=4 和 j=5 变化 S to AABAB.
因此,您可以使 S 等于 T 有两个操作。可以证明这是最少需要的运算次数,所以答案是 2.
示例输入 2
2 AB BA
示例输出 2
-1
可以证明,无论执行多少次操作,都无法使 S 等于 T.