C - 魂の還る場所 解説 /

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

高橋君が大好きなプラスチック製の円筒と不思議な赤青緑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