AT_agc069_c [AGC069C] AB*A Changing

题目描述

现有两个长度为 $N$ 的字符串 $S$ 和 $T$，它们都只由字符 A 和 B 组成。我们用 $s_i$ 来表示字符串 $S$ 的第 $i$ 个字符。

对于字符串 $S$，你可以反复进行以下操作不限次数：

• 选择两个整数 $(i, j)$，要求满足：

  • $1 \leq i < j \leq N$
  • $s_i = s_j = \text{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。

输入格式

输入从标准输入中提供，格式为：

$N$ $S$ $T$

输出格式

如果可以通过操作将字符串 $S$ 变为 $T$，输出最少需要的操作次数；如果无法做到，输出 -1。

输入输出样例 #1

输入 #1

5
AAABA
BAAAB

输出 #1

2

输入输出样例 #2

输入 #2

1
A
B

输出 #2

-1

输入输出样例 #3

输入 #3

1
A
A

输出 #3

0

输入输出样例 #4

输入 #4

10
AAABBABAAB
BBABBAAABB

输出 #4

7

说明/提示

• $1 \leq N \leq 200,000$
• $S, T$ 均为由 A 和 B 组成的长度为 $N$ 的字符串

示例说明

示例 1

通过下面的操作，可以用 2 次将 $S$ 变为 $T$：

1. 选择 $(i, j) = (2, 3)$，此时 $S$ 变为 ABBBA。
2. 选择 $(i, j) = (1, 5)$，此时 $S$ 变为 BAAAB。

所以，最少操作次数为 2。

示例 2

不能通过任何操作将 $S$ 变为 $T$，因而答案是 -1。注意：要求 $i < j$。

示例 3

此时 $S$ 和 $T$ 本来就相同，不需任何操作。

本翻译由 AI 自动生成