2911. Minimum Changes to Make K Semi-palindromes
Difficulty: Hard
Topics: Principal , Two Pointers , String , Dynamic Programming , Weekly Contest 368
Given a string s and an integer k , partition s into k substrings 1 such that the letter changes needed to make each substring a semi-palindrome are minimized.
Return the minimum number of letter changes required .
A semi-palindrome is a special type of string that can be divided into palindromes 2 based on a repeating pattern. To check if a string is a semi-palindrome:
Choose a positive divisor d of the string's length. d can range from 1 up to, but not including, the string's length. For a string of length 1 , it does not have a valid divisor as per this definition, since the only divisor is its length, which is not allowed.
For a given divisor d , divide the string into groups where each group contains characters from the string that follow a repeating pattern of length d .…