Citadel OA Interview Question: Minimum Changes to Make a String a Palindrome with Period k

Question 2

The current password is represented by the string currentPassword, consisting only of lowercase Latin letters.

New password requirements have just been released.

The new password, called newPassword, must meet two specific requirements:

• It must be a palindrome.
• It must have a period of k. That is, newPassword[i] = newPassword[i + k], for all 1 <= i <= length(newPassword) - k.

The objective is to determine the minimum number of characters that need to be changed in currentPassword to create a newPassword of the same length.

Example

currentPassword = "abzzbz"
k = 3

Changing the first character of currentPassword to 'z' creates a newPassword of "zbzzbz", which is a palindrome with a period of 3. Therefore, the answer is 1.

Function Description

Complete the function findMinChanges in the editor with the following parameters:

• string currentPassword: the current password
• int k: the required period of the new password

Returns

• int: the minimum number of characters to change to make a valid newPassword

Sample Input 0

cbpecbbc
4

Sample Output 0

2

Explanation

Changing the third and fourth characters to 'c' and 'b' respectively makes newPassword = "cbbccbbc", which is a palindrome with period four.

Sample Input 1

vsvvsv
3

Sample Output 1

0

The key idea is to merge all positions that must end up equal because of the period-k rule and the palindrome constraint. Once the positions are grouped, each group can be solved independently: count the frequency of each letter, keep the most common one, and change the rest. Summing these minimum changes over all groups gives the answer. This is a grouping/union-style counting problem with a greedy choice inside each group.