Minimize Changes to Make Every Password Block Palindromic

Problem Statement

You are given a string password consisting of lowercase English letters and an integer k.

The password is partitioned into consecutive, non-overlapping blocks of length k. You are guaranteed that the length of password is a multiple of k.

In a single operation, you can change any character in password to any other lowercase English letter. The block boundaries are fixed and cannot be shifted.

Return the minimum number of character changes required such that every block of length k is a palindrome.

Function Interface

def min_changes_to_palindromic_blocks(password: str, k: int) -> int:
    pass

Input & Output Format

• Input:
  • password: A string of lowercase English letters ('a' - 'z').
  • k: An integer representing the block size.
• Output:
  • An integer representing the minimum number of character replacements.

Constraints

• 1 <= k <= len(password) <= 2 * 10^5
• len(password) % k == 0
• password consists only of lowercase English letters.

Examples

Example 1

Input: password = "abcbadeba", k = 3
Output: 3
Explanation:
The string is divided into 3 blocks of length 3:
- Block 1: "abc" -> can be changed to "aba" (1 change: 'c' -> 'a')
- Block 2: "bad" -> can be changed to "bab" (1 change: 'd' -> 'b')
- Block 3: "eba" -> can be changed to "ebe" (1 change: 'a' -> 'e')
Total changes = 1 + 1 + 1 = 3.

Example 2

Input: password = "racecarannana", k = 7
Output: 1
Explanation:
The string is divided into 2 blocks of length 7:
- Block 1: "racecar" is already a palindrome (0 changes).
- Block 2: "annana" has length 6? Here k = 7, so suppose password is "racecarannaana".
  "racecar" (0 changes) and "annaana" (already a palindrome, 0 changes).
For password = "racecarxyzzaa", k = 7:
- Block 1: "racecar" (0 changes)
- Block 2: "xyzzaa" -> 'x' != 'a' (1 change), 'y' != 'a' (1 change), 'z' == 'z' (0 changes). Total = 2.

Example 3

Input: password = "aaaa", k = 2
Output: 0
Explanation: Both blocks "aa" and "aa" are already palindromes.

Edge Cases

• k = 1: Every single character is trivially a palindrome; 0 changes are always needed.
• k = len(password): The entire string is treated as a single block.
• The password is already composed of palindromic blocks.