A - Make UTPC
Editorial
/


Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : {100} 点
問題文
4 種類の文字 U
, T
, P
, C
からなる長さ N の文字列 S が与えられます。
あなたは、次の操作を好きな回数行うことが出来ます。
- 整数 i, j \, (1 \leq i < j \leq N) を選ぶ。S の i 番目の文字と j 番目の文字を入れ替える。
文字列 S が以下の条件を満たすようにするために必要な操作回数の最小値を求めてください。
- S は連続部分文字列として
UTPC
を含む。
ただし、S は U
, T
, P
, C
をそれぞれ 1 つ以上含むことが保証されます。
制約
- 4 \leq N \leq 10000
- S は
U
,T
,P
,C
からなる長さ N の文字列 - S は
U
,T
,P
,C
をそれぞれ 1 つ以上含む
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
文字列 S が条件を満たすようにするために必要な操作回数の最小値を出力せよ。
入力例 1
5 UTCUP
出力例 1
2
UTCUP
\rightarrow UTPUC
\rightarrow UTPCU
のように 2 回操作を行うと、1 文字目から 4 文字目までが UTPC
となるため、S が条件を満たします。
入力例 2
4 UTPC
出力例 2
0
最初から条件を満たす場合、0 を出力してください。
入力例 3
20 PTPUTPTUCPTUPTUPCTPC
出力例 3
1