分数: 1500 点
问题陈述
一个字符串,由字母组成 A, B,和 C,称为 好,如果每两个连续字母不同。例如,字符串 ABABAB 和 ABC 很好,同时 ABBA 和 AABBCC 不是。
你有两个 好 字符串 S 和 T 长度 N。
在一次操作中,您可以选择以下任意字母 S,并将其更改为其中的另一个字母 A, B,和 C,这样 S 仍然存在 好.
转换所需的最少操作数是多少 S 进入 T? 我们可以证明它总是可以通过有限次数的操作来完成。
约束
- 1\le N \le 5\cdot 10^5
- S 是 好 长度的字符串 N 组成
A,B,和C - T 是 好 长度的字符串 N 组成
A,B,和C
输入
输入由标准输入按以下格式给出:
N S T
输出
输出变换所需的最少操作数 S 进入 T.
样本输入 1
4 CABC CBAC
示例输出 1
6
这是一种可能的长度操作序列 6:
CABC \to BABC \to BCBC \to BCAC \to ACAC \to ABAC \to CBAC
可以证明 6 对于这种情况需要进行操作。
示例输入 2
10 ABABABABAB BABABABABA
示例输出 2
15