No.1951 Vanished AGCT (2)
Problem Statement
A string $s$ of $n$ characters consisting only of uppercase English letters is given as input.
You perform operations so that $s$ satisfies the condition. Output the minimum number of operations required.
Condition: $s$ does not contain any of the characters A,G,C,T
Performing the following steps 1. through 5. in order counts as one operation. You may not reorder the steps or skip any particular step.
Operation:
- Let $c_1$ be the total number of characters
A,G,C,Tcontained in $s$ - Let $t$ be the string obtained by deleting the $c_1$-th character of $s$
- Let $c_2$ be the number of occurrences in $t$ of the $c_1$-th character of $s$
- Perform $c_2$ times the operation of replacing each character of $t$ with the next character in alphabetical order
Here, the character $1$ position afterZin alphabetical order is considered to beA - Replace $s$ with $t$
Input
$n$ $s$
Constraints
- $ 1 \le n \le 5 \times10^{5}$
- $|s|=n$
- $s$ consists only of uppercase English letters
- $n$ is an integer
Output
Output the minimum number of operations required until the condition is satisfied.
Print a newline at the end.
Sample
Sample 1
Input
11 ABRACADABRA
Output
2
The string changes as ABRACADABRA→EFVEGHEFVE→IYHJKHIYH.
Sample 2
Input
9 YUKICODER
Output
5
Sample 3
Input
19 ATCODERGRANDCONTEST
Output
18
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
H20
蜜蜂
naskya