Minimize changes for k-periodic palindrome
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### 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/
Quick Answer: This question evaluates understanding of string algorithms and combinatorial reasoning, focusing on palindrome properties combined with k-periodicity and the ability to minimize character changes under global constraints.
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
Input: ('abca', 2)
Expected 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.
Input: ('abbaabba', 4)
Expected Output: 0
Explanation: The string already repeats every 4 characters and is also a palindrome, so no changes are needed.
Hints
- Because the string must be k-periodic, all positions with the same index modulo k must end up equal.
- 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.