1332C.md (1920B)
1 Source: https://codeforces.com/problemset/problem/1332/C 2 3 C. K-Complete Word 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Word $s$ of length $n$ is called $k$-complete if 22 23 * $s$ is a palindrome, i.e. $s_i=s_{n+1-i}$ for all $1 \le i \le n$; 24 * $s$ has a period of $k$, i.e. $s_i=s_{k+i}$ for all $1 \le i \le n-k$. 25 26 For example, "abaaba" is a $3$-complete word, while "abccba" is not. 27 28 Bob is given a word $s$ of length $n$ consisting of only lowercase Latin letters and an integer $k$, such that $n$ is divisible by $k$. He wants to convert $s$ to any $k$-complete word. 29 30 To do this Bob can choose some $i$ ($1 \le i \le n$) and replace the letter at position $i$ with some other lowercase Latin letter. 31 32 So now Bob wants to know the minimum number of letters he has to replace to convert $s$ to any $k$-complete word. 33 34 Note that Bob can do zero changes if the word $s$ is already $k$-complete. 35 36 You are required to answer $t$ test cases independently. 37 38 Input 39 40 The first line contains a single integer $t$ ($1 \le t\le 10^5$) — the number of test cases. 41 42 The first line of each test case contains two integers $n$ and $k$ ($1 \le k \lt n \le 2 \cdot 10^5$, $n$ is divisible by $k$). 43 44 The second line of each test case contains a word $s$ of length $n$. 45 46 It is guaranteed that word $s$ only contains lowercase Latin letters. And it is guaranteed that the sum of $n$ over all test cases will not exceed $2 \cdot 10^5$. 47 48 Output 49 50 For each test case, output one integer, representing the minimum number of characters he has to replace to convert $s$ to any $k$-complete word. 51 52 Example 53 54 Input 55 56 ``` 57 4 58 6 2 59 abaaba 60 6 3 61 abaaba 62 36 9 63 hippopotomonstrosesquippedaliophobia 64 21 7 65 wudixiaoxingxingheclp 66 ``` 67 68 Output 69 70 ``` 71 2 72 0 73 23 74 16 75 ``` 76 77 Note 78 79 In the first test case, one optimal solution is aaaaaa. 80 81 In the second test case, the given word itself is $k$-complete.