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 all1 <= 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 = 3Changing 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 passwordint k: the required period of the new password
Returns
int: the minimum number of characters to change to make a validnewPassword
Sample Input 0
cbpecbbc
4Sample Output 0
2Explanation
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
3Sample Output 1
0这题的关键是把“周期为 k”和“回文”两个约束合并到同一组等价字符上：长度相同、每隔 k 位置相同，意味着字符串会被划分成若干个按下标模 k 的分组；再加上回文要求，左右对称的位置也必须属于同一个最终字符集合。做法通常是先把所有被约束到一起的位置归并为一个连通块 / 分组，然后在每组内统计 26 个字母出现次数，保留出现次数最多的字母，其余字符都需要修改。把每组的修改代价累加，就是答案。这个思路本质上是“并查集 / 分组 + 频次统计 + 贪心选择众数”，能高效处理较长字符串。
