問題一覧 > 通常問題

No.1943 消えたAGCT(1)

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

問題文

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

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

条件:$s$ にA,G,C,Tの文字が含まれない

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

操作:

  1. $s$ に含まれる A,G,C,Tの文字数の合計を $c$ とする
  2. $s$ の $c$ 文字目を削除した文字列を $t$ とする
  3. $s$ を $t$ に置き換える

入力

$n$
$s$

制約

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

出力

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

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

サンプル

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

ABCDEFACDEFADEFDEFと置き換わります。

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

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

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

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