← 返回题目列表

AtCoder · arc002_3

C. 指令输入

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

問題文

高桥决定和他的朋友们一起玩格斗游戏。
格斗游戏 A, B, X, Y 的 4 这是一款格斗游戏,您可以使用通过连续按下不同按钮输入的命令来执行技术。
然而,对于平时不玩格斗游戏的高桥来说,输入命令很困难,他不认为自己能打败他的朋友。
那里有盈余。 L 和 将其放在 R 连续按钮 2 我想通过将两个按钮输入分配为快捷方式来缩短输入命令所需的时间。
例如,命令 ABXY 您需要输入按钮 4 次,L 至 通过分配 AB、R 至 通过分配 XY 这可以减少为 LR 的 2 按钮输入。 使用
L 和 将其放在 R 查找输入尽可能短时所需的按钮输入数量。

入力

输入将以以下形式通过标准输入给出。
N
c_{1}c_{2}...c_{N}
  • 1 行指示命令所需的按钮输入数量。 给出 N(1 ≦ N ≦ 1000)。
  • 2 行代表命令的内容。 N 给出一个字符串。
  • i 是字符 c_{i} 是A, B, X, Y 。

出力

当使用快捷键最小化命令输入所需的按钮输入数量时,按钮输入的数量将作为标准输出输出。 1 行输出。
请在末尾输出换行符。 通过分配

入力例 1

4
ABXY

出力例 1

2
  • L 至 通过分配 AB、R 至 通过分配 XY 输入 可缩写为 LR ,按钮输入数量为 2 次。

入力例 2

13
ABABABABXBXBX

出力例 2

7
  • L 至 通过分配 AB、R 至 通过分配 BX 输入 可缩写为 LLLARRR ,按钮输入数量为 7 次。

入力例 3

8
AABBAABB

出力例 3

4
  • L 至 通过分配 AA、R 至 通过分配 BB 输入 可缩写为 LRLR ,按钮输入数量为 4 次。