← 返回题目列表

AtCoder · agc069_c

C. AB*A 改变

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

分数: 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 分两次操作如下:

  1. 执行操作 (i, j) = (2, 3). S 变为 ABBBA.
  2. 执行操作 (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