Minimize changes for k-periodic palindrome

Question

Given a string currentPassword (length N) and an integer k (1 ≤ k < N, N ≤ 2·10^5, lowercase letters, N divisible by k), find the minimum number of character changes needed to transform currentPassword into a newPassword such that (1) newPassword is a palindrome and (2) newPassword[i] = newPassword[i + k] for all valid i (k-periodic). Return that minimum number of changes.

https://www.geeksforgeeks.org/minimum-replacements-required-to-obtain-a-k-periodic-palindromic-string/

Minimize Changes for K-Periodic Palindrome

Given a lowercase string currentPassword of length N and an integer k, find the minimum number of character replacements needed to transform it into a new string newPassword such that: (1) newPassword is a palindrome, and (2) newPassword is k-periodic, meaning newPassword[i] = newPassword[i + k] for every valid i. Each replacement changes one character to any lowercase letter and costs 1. Return the minimum total cost.

Constraints

• 1 <= k < N <= 2 * 10^5
• N is divisible by k
• currentPassword contains only lowercase English letters

Examples

Example 1

Input: ('abca', 2)
Output: 2

Explanation: With k = 2, residues 0 and 1 must mirror each other, so all 4 positions belong to one group. The letters are a, b, c, a; keeping 'a' and changing the other two costs 2.

Example 2

Input: ('abbaabba', 4)
Output: 0

Explanation: The string already repeats every 4 characters and is also a palindrome, so no changes are needed.

Hints

1. Because the string must be k-periodic, all positions with the same index modulo k must end up equal.
2. Use the palindrome condition to see which modulo-k positions must match each other, then choose the most frequent character in each forced-equality group.