codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.