問題一覧 > 通常問題

No.1943 消えたAGCT(1)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 202
作問者 : H20 / テスター : 蜜蜂 naskya
4 ProblemId : 7916 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-05-05 15:27:07

問題文

英大文字のみからなる nn 文字の文字列 ss が入力として与えられます。

ss が条件を満たすように操作を行います。必要な操作の最小の回数を出力してください。

条件ssA,G,C,Tの文字が含まれない

以下の 1. から 3. までの手順を順番に通して行うことを一回の操作とします。手順を入れ替えたり、特定の手順を省略したりすることはできません。

操作:

  1. ss に含まれる A,G,C,Tの文字数の合計を cc とする
  2. sscc 文字目を削除した文字列を tt とする
  3. sstt に置き換える

入力

nn
ss

制約

  • 1n5×105 1 \le n \le 5 \times 10^{5}
  • s=n|s|=n
  • ss は英大文字のみからなる
  • nn は整数

出力

条件を満たすまでに必要な操作の最低回数を出力してください。

最後に改行してください。

サンプル

サンプル1
入力
6
ABCDEF
出力
3

ABCDEFACDEFADEFDEFと置き換わります。

サンプル2
入力
9
YUKICODER
出力
5

サンプル3
入力
19
ATCODERGRANDCONTEST
出力
19

サンプル4
入力
3
XYZ
出力
0

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。