問題一覧 > 通常問題

No.2073 Concon Substrings (Swap Version)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 113
作問者 : 👑 AngrySadEightAngrySadEight / テスター : sapphire__15sapphire__15
0 ProblemId : 8299 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-09-16 16:55:22

問題文

英小文字からなる長さ 3N3N の文字列 SS が与えられます.この文字列 SS に対して,次に示す操作を,00 回以上の好きな回数行うことができます.

  • 操作: 1i3N31 \leq i \leq 3N - 3 なる整数 ii をひとつ選ぶ.SiS_iSi+3S_{i+3} を入れ替える.

ただし,SiS_i で文字列 SS の左から ii 番目の文字を表します.

操作後の SS の中に含まれる連続する部分列 con の個数の最大値を求めてください.

入力

NN
SS

  • NN は整数である.
  • 1N2×1051 \leq N \leq 2 \times 10^5
  • SS は英小文字からなる長さ 3N3N の文字列である.

出力

答えを出力せよ.

サンプル

サンプル1
入力
3
toscenter
出力
1

次のように操作を行えばよいです.

  • i=1i=1 を選び,S1S_1S4S_4 を入れ替える.toscentercostenter となる.
  • i=3i=3 を選び,S3S_3S6S_6 を入れ替える.costentercontester となる.
このようにして操作を行うことで,文字列 SS に含まれる連続する部分列 con の個数は 11 になり,これが最大です.

サンプル2
入力
3
conconfox
出力
2

操作を行うまでもなく,文字列 conconfox に含まれる連続する部分列 con の個数は 22 となり,これが最大です.

サンプル3
入力
5
kudagitsunecoon
出力
0

どのように操作を行っても,連続する部分列 con を作ることはできません.

サンプル4
入力
9
yukicoderprogrammingcontest
出力
2

サンプル5
入力
33
paracetamoxyfrusebendroneomycinsupercalifragilisticexpialidocioussupercalifragilisticexpialidocious
出力
3

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