K-Complete Word (Codeforces 1332C)
Tags: Greedy, dsu

Word $$$s$$$ of length $$$n$$$ is called $$$k$$$-complete if   $$$s$$$ is a palindrome, i.e. $$$s_i=s_{n+1-i}$$$ for all $$$1 \le i \le n$$$;  $$$s$$$ has a period of $$$k$$$, i.e. $$$s_i=s_{k+i}$$$ for all $$$1 \le i \le n-k$$$. For example, "abaaba" is a $$$3$$$-complete word, while "abccba" is not.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.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.So now Bob wants to know the minimum number of letters he has to replace to convert $$$s$$$ to any $$$k$$$-complete word.Note that Bob can do zero changes if the word $$$s$$$ is already $$$k$$$-complete.You are required to answer $$$t$$$ test cases independently.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t\le 10^5$$$) — the number of test cases.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k < n \le 2 \cdot 10^5$$$, $$$n$$$ is divisible by $$$k$$$).The second line of each test case contains a word $$$s$$$ of length $$$n$$$.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$$$.

Output: 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.

Note: In the first test case, one optimal solution is aaaaaa.In the second test case, the given word itself is $$$k$$$-complete.

Sample Inputs:
4
6 2
abaaba
6 3
abaaba
36 9
hippopotomonstrosesquippedaliophobia
21 7
wudixiaoxingxingheclp

Sample Outputs:
2
0
23
16

Solution (Python):
from collections import defaultdict, deque
import sys
input = sys.stdin.readline

def solve():
    (n, k) = map(int, input().split())
    s = input().strip()
    (res, vis) = (0, [0] * n)
    for i in range(n):
        if vis[i]:
            continue
        q = deque([i])
        vis[i] = True
        cnt = [0] * 26
        while q:
            ii = q.popleft()
            cnt[ord(s[ii]) - ord('a')] += 1
            for ni in [ii + k, ii - k, n - ii - 1]:
                if 0 <= ni < n and vis[ni] == False:
                    vis[ni] = True
                    q.append(ni)
        res += sum(cnt) - max(cnt)
    print(res)
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
input = sys.stdin.readline

def readList():
    return list(map(int, input().split()))

def readInt():
    return int(input())

def readInts():
    return map(int, input().split())

def readStr():
    return input().strip()

def solve():
    (n, k) = readInts()
    s = readStr()
    graph = [[] for _ in range(n)]
    for i in range(n):
        if i < n // 2:
            graph[i].append(n - 1 - i)
            graph[n - 1 - i].append(i)
        if i + k < n:
            graph[i].append(i + k)
            graph[i + k].append(i)
    ans = 0
    vis = [0] * n
    for i in range(n):
        if vis[i]:
            continue
        (vis[i], count, st) = (1, [0] * 26, [i])
        while st:
            node = st.pop()
            count[ord(s[node]) - ord('a')] += 1
            for nei in graph[node]:
                if vis[nei]:
                    continue
                vis[nei] = 1
                st.append(nei)
        ans += sum(count) - max(count)
    return ans
for _ in range(readInt()):
    print(solve())

Solution (Python):
def main():
    return '\n'.join((nCharactersToReplaceMin() for _ in range(int(input()))))

def nCharactersToReplaceMin():
    (word_sLength, period) = map(int, input().split())
    limit = period // 2
    if period % 2:
        (word, middleLettersCount) = (input(), {})
        for i in range(limit, word_sLength, period):
            if word[i] not in middleLettersCount:
                middleLettersCount[word[i]] = 1
            else:
                middleLettersCount[word[i]] += 1
        return str(word_sLength - max(middleLettersCount.values()) - nDesiredCharacters(word, period, limit, limit))
    else:
        return str(word_sLength - nDesiredCharacters(input(), period, limit, limit - 1))

def nDesiredCharacters(word, period, limit1, limit2):
    return sum((countOfMostRepeatedCharacter(word, period, i1, i2) for (i1, i2) in zip(range(limit1), range(period - 1, limit2, -1))))

def countOfMostRepeatedCharacter(word, period, i1, i2):
    lettersCount = {}
    for (j1, j2) in zip(range(i1, len(word), period), range(i2, len(word), period)):
        if word[j1] not in lettersCount:
            lettersCount[word[j1]] = 1
        else:
            lettersCount[word[j1]] += 1
        if word[j2] not in lettersCount:
            lettersCount[word[j2]] = 1
        else:
            lettersCount[word[j2]] += 1
    return max(lettersCount.values())
if __name__ == '__main__':
    print(main())