CF1332C K-Complete Word

长度为 $n$ 的单词 $s$ 被称为 $k$-完全（$k$-complete），如果满足以下两个条件： - $s$ 是回文串，即对于所有 $1 \le i \le n$，都有 $s_i = s_{n+1-i}$； - $s$ 具有周期 $k$，即对于所有 $1 \le i \le n-k$，都有 $s_i = s_{k+i}$。 例如，"abaaba" 是一个 $3$-完全单词，而 "abccba" 不是。 Bob 得到一个长度为 $n$ 的单词 $s$，仅包含小写拉丁字母，以及一个整数 $k$，其中 $n$ 能被 $k$ 整除。他想将 $s$ 转换为任意一个 $k$-完全单词。 为此，Bob 可以选择某个位置 $i$（$1 \le i \le n$），并将该位置的字母替换为任意其他小写拉丁字母。 现在，Bob 想知道，最少需要替换多少个字母，才能将 $s$ 转换为任意一个 $k$-完全单词。 注意，如果单词 $s$ 已经是 $k$-完全的，则可以不进行任何操作。 你需要独立回答 $t$ 组测试用例。

第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。 每组测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k < n \le 2 \times 10^5$，$n$ 能被 $k$ 整除）。 每组测试用例的第二行包含一个长度为 $n$ 的单词 $s$。 保证单词 $s$ 只包含小写拉丁字母。并且保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试用例，输出一个整数，表示将 $s$ 转换为任意一个 $k$-完全单词所需替换的最小字母数。

在第一个测试用例中，一种最优方案是将所有字母都变为 a，得到 "aaaaaa"。 在第二个测试用例中，给定的单词本身就是 $k$-完全的。 由 ChatGPT 4.1 翻译