← 返回题目列表

AtCoder · arc014_3

C. 灵魂归来的地方

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

問題文

高桥最喜欢的塑料圆柱体和神秘的红、蓝、绿3有彩球。
这个球的大小勉强可以放入圆柱体中。
为了方便起见,我们将圆柱体的两端称为“右”和“左”,这样您就可以从左或右插入球。
该球具有当与相同颜色的球接触时消失的属性。
此外,这些 3 当仅确定一种颜色的多个球的放置顺序时,放置所有球后剩余的球的数量根据每个球是从左还是从右放置而变化。

3 如果只给出每种颜色的多个球的放置顺序,并计划在最后使圆柱体中剩余的球数最少,那么圆柱体中剩余的最小球数是多少?

入力

输入将以以下形式通过标准输入给出。
N
S
  1. 1 行是表示球数的整数。 N(1≦N≦50) 。 来自行
  2. 2 该行中球的放置顺序是 给出 S , R 为红色; G 为绿色; B 代表一个蓝色球。 S 是 R, G, B 的 3 仅限类型字符 N 由字符组成。 如果仅对满足

部分点

  • 1≦N≦15 的输入给出正确答案,则部分点为 30 分被给予。

出力

当计划最小化最后剩余的球数时,剩余的最小数量为 它应该输出为 1 行。
另外,在输出末尾放置一个换行符。

入力例 1

9
RGBGGBGBR

出力例 1

1
  • 第一 输入 R 。 从左侧插入 R
  • 下一步 G 。 从右侧插入 GR
  • B 。 GRB
  • G 。 GRBG
  • G 。 GRBGG
    • 此时 它消失是因为 G 已对齐。 GRB
  • B 。 GRBB
    • 此时 它消失是因为 B 已对齐。 GR
  • G 。 从右侧插入 GGR
    • 此时 它消失是因为 G 已对齐。 R
  • B 。 从右侧插入 BR
  • R 。 BRR
    • 此时 它消失是因为 R 已对齐。 B
  • 因此 B 是 从1还剩一个,所以答案是1。

入力例 2

6
RGBRGB

出力例 2

0