← 返回题目列表

AtCoder · abc421_c

F. 交替

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

分数: 350 点

问题陈述

给你一个字符串 S 长度 2N. S 恰好包含 N 出现次数 A 和 N 出现次数 B.

找到完成所需的最小操作数(可能为零) S 没有相邻的相同字符,其中操作包括交换两个相邻字符 S.

约束

  • 1\leq N \leq 5\times 10^5
  • N 是一个整数。
  • S 是一个长度为的字符串 2N 组成 N 出现次数 A 和 N 出现次数 B.

输入

输入由标准输入按以下格式给出:

N
S

输出

打印答案。


示例输入 1

3
AABBBA

示例输出 1

2

通过执行如下操作,可以达到两次操作中不存在相邻相同字符的状态:

  • 交换 2nd 和 3rd 字符。 S 变为 ABABBA.
  • 交换 5日和 6个字符。 S 变为 ABABAB.

示例输入 2

3
AAABBB

示例输出 2

3

请注意,您只能交换相邻的字符。


示例输入 3

17
AAABABABBBABABBABABABABBAAABABABBA

示例输出 3

15