#2911
Minimum Changes to Make K Semi-palindromes
master · 1855 · lc hard +32 · 36.2% accepted · 131 likes · top 14%
Description
A string s and an integer k are given. Partition s into exactly k substrings to minimize the total character changes needed to make each substring a semi-palindrome.
A semi-palindrome can be verified as follows:
- Choose a divisor d of the string's length where 1 <= d < length. (Single-character strings have no valid divisor.)
- Group characters by their positions modulo d: group r holds characters at indices r, r+d, r+2d, ....
- The string is semi-palindrome if every such group forms a palindrome.
For example, "abcabc" with d = 3 yields groups "aa", "bb", "cc", all palindromes, so it qualifies.
Return the minimum total changes required.
Code
1
2
3