FPC25-027.Characterithmetic

While solving one problem after the other in your favourite programming contest (hopefully, the one you are at right now!), you are suddenly faced with an Alternative Arithmetic Problem for the Jury's Entertainment. In this problem, you are not calculating with numbers, but with strings.

For some arbitrary string $t$ and integer $k$, we define $t\odot k$ ($t$ times $k$) to be the string $t$ concatenated $k$ times. If $t$ can be written as $t' \odot k$ for some other string $t'$, we say that $k$ is a divisor of $t$. For example, the divisors of the string “abababab” are $1$, $2$, and $4$, because this string can be written as either $\text{``\texttt{abababab}''} \odot 1$, or $\text{``\texttt{abab}''} \odot 2$, or $\text{``\texttt{ab}''} \odot 4$. Finally, we say that a string is indivisible if its only divisor is $1$: for example, the string “abc” is indivisible.

You are given a string $s$ of length $n$, that contains only the characters ‘a’, ‘b’, and ‘c’. For each divisor $d$ of $n$, you need to change some of the characters (to either ‘a’, ‘b’, or ‘c’), so that the largest divisor of $s$ becomes $d$. Find the minimum number of characters that need to be changed in order to make this true.

As an example, consider the first sample input. There are three answers, one for each of the divisors of $4$:

• To make the largest divisor of “acac” be $1$, we need to make sure that $2$ is not a divisor. We can change any character to make the string indivisible, e.g. “bcac”.

• The largest divisor of “acac” is already $2$, so no characters need to change and the answer is $0$.

• To make the largest divisor $4$, we need to make all characters equal. To do this, $2$ characters need to be changed, yielding either “aaaa” or “cccc”.