問題一覧 > 通常問題

No.2073 Concon Substrings (Swap Version)

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

問題文

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

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

ただし,$S_i$ で文字列 $S$ の左から $i$ 番目の文字を表します.

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

入力

$N$
$S$

  • $N$ は整数である.
  • $1 \leq N \leq 2 \times 10^5$
  • $S$ は英小文字からなる長さ $3N$ の文字列である.

出力

答えを出力せよ.

サンプル

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

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

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

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

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

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

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

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

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

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