P8739 [Lanqiao Cup 2020 National C] Repeated String

If a string $S$ can be obtained exactly by repeating some string $K$ times, then we call $S$ a $K$-times repeated string. For example, `abcabcabc` can be seen as repeating `abc` for $3$ times, so `abcabcabc` is a $3$-times repeated string. Similarly, `aaaaaa` is a $2$-times repeated string, a $3$-times repeated string, and also a $6$-times repeated string. Now given a string $S$, please compute the minimum number of characters that need to be modified so that $S$ becomes a $K$-times repeated string.

The first line contains an integer $K$. The second line contains a string $S$ consisting only of lowercase letters.

Output an integer as the answer. If $S$ cannot be modified into a $K$-times repeated string, output $-1$.

Constraints: $1 \le K \le 10^5$, $1 \le |S| \le 10^5$. Here $|S|$ denotes the length of $S$. Lanqiao Cup 2020 National Contest Group C, Problem G. Translated by ChatGPT 5