考察

• 文字 x を置換すると、置換後の文字列に現れる x の個数は A, B, C の中で最小になる
• 置換後の文字列に現れる “ABC” は全て置換で追加されたものである

解法

• 「S に現れる “ABC” を全て、頻度最小の文字に置換する」を繰り返す
• ステップ数は高々 \(|S|\) 回なので \(O(|S|^2)\)