← 返回题目列表

AtCoder · tkppc6_2_b

B. 更换为其他

中文机器翻译题面 查看原题

配点 : 400 点

問題文

A, B 组成的长度 给出了 N 字符串 S, T 。执行以下操作 通过重复 0 超过 判断是否可以匹配 S 的 T ,如果可以,求所需的最少运算次数。 一个整数,使得

  • S_i=S_{i+1} 选择 i\ (1 \leq i \lt N) , 将S_i 和 S_{i+1} 的 A, B 中的每个字符替换为与当前字符不同的字符。

制約

  • 2 \leq N \leq 2 \times 10^5
  • S, T 是 A, B 组成的长度 给出了 N 字符串

入力

输入是按以下格式从标准输入给出的。

N
S
T

出力

通过问题文本中的操作 若能与 S 的 T 匹配,则最少需要运算次数为 -1 。


入力例 1

3
AAB
BAA

出力例 1

2

例如,最好按照以下步骤操作。 执行

  • i=1 操作。S 是 BBB 。另外,数列
  • i=2 操作。S 是 BAA ,即 匹配 T 。

入力例 2

3
ABA
AAA

出力例 2

-1

首先,我连一次都无法执行该操作, 您无法匹配S 的 T ,所以-1 。


入力例 3

4
ABAB
ABAB

出力例 3

0

S 和 T 已经匹配,因此您根本不需要执行任何操作。

原案: 夏美曾严