No.2073 Concon Substrings (Swap Version)
タグ : / 解いたユーザー数 113
作問者 : 👑
sapphire__15
Problem Statement
You are given a string $S$ of length $3N$ consisting of lowercase English letters. You may perform the following operation on this string $S$ any number of times, possibly $0$ times.
- Operation: Choose one integer $i$ such that $1 \leq i \leq 3N - 3$. Swap $S_i$ and $S_{i+3}$.
Here, $S_i$ denotes the $i$-th character from the left of the string $S$.
Find the maximum possible number of contiguous substrings con contained in $S$ after the operations.
Input
$N$ $S$
- $N$ is an integer.
- $1 \leq N \leq 2 \times 10^5$
- $S$ is a string of length $3N$ consisting of lowercase English letters.
Output
Output the answer.
Sample
Sample 1
Input
3 toscenter
Output
1
You can perform the operations as follows.
- Choose $i=1$ and swap $S_1$ and $S_4$.
toscenter→costenter. - Choose $i=3$ and swap $S_3$ and $S_6$.
costenter→contester.
con contained in the string $S$ becomes $1$, which is the maximum.
Sample 2
Input
3 conconfox
Output
2
Even without performing any operations, the number of contiguous substrings con contained in the string conconfox is $2$, which is the maximum.
Sample 3
Input
5 kudagitsunecoon
Output
0
No matter how you perform the operations, you cannot create a contiguous substring con.
Sample 4
Input
9 yukicoderprogrammingcontest
Output
2
Sample 5
Input
33 paracetamoxyfrusebendroneomycinsupercalifragilisticexpialidocioussupercalifragilisticexpialidocious
Output
3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。