KSA String

Interview

Time limit1sMemory limit1024 MB

Summary

Given a string X, find the fewest deletions and front or end insertions that turn it into the KSA-periodic string of the same length.

Level: Medium4 of 10
Topics: String, Greedy
Solved: No attempts yet

Problem

The KSAAC staff all love KSA, so they like strings that satisfy the following condition.

Let the length of the string be $N$ . For every $i$ with $1\leq i\leq N$ :

If the remainder of $i$ divided by $3$ is $1$ , the $i$ -th character is K.
If the remainder of $i$ divided by $3$ is $2$ , the $i$ -th character is S.
If the remainder of $i$ divided by $3$ is $0$ , the $i$ -th character is A.

You can perform the following operations on a string zero or more times.

Remove one existing character.
Add one arbitrary character at the front.
Add one arbitrary character at the end.

Perform appropriate operations on the given string $X$ to turn it into a string of the same length as $X$ that the KSAAC staff like. Find the minimum number of operations needed.

Input

The first line contains the string $X$ .

Output

Print the minimum number of operations needed to turn $X$ into a string of the same length as $X$ that the KSAAC staff like.

Constraints

$1\leq |X|\leq 5\times 10^5$
$X_i \in \{K, S, A\}$

Examples1

Example 1
Input
```
KKSKASKA
```
Expected output
```
8
```