Description
Given a string s
and an integer k
, partition s
into k
substrings 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 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 from1
up to, but not including, the string's length. For a string of length1
, 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 lengthd
. Specifically, the first group consists of characters at positions1
,1 + d
,1 + 2d
, and so on; the second group includes characters at positions2
,2 + d
,2 + 2d
, etc. - The string is considered a semi-palindrome if each of these groups forms a palindrome.
Consider the string "abcabc"
:
- The length of
"abcabc"
is6
. Valid divisors are1
,2
, and3
. - For
d = 1
: The entire string"abcabc"
forms one group. Not a palindrome. - For
d = 2
:- Group 1 (positions
1, 3, 5
):"acb"
- Group 2 (positions
2, 4, 6
):"bac"
- Neither group forms a palindrome.
- Group 1 (positions
- For
d = 3
:- Group 1 (positions
1, 4
):"aa"
- Group 2 (positions
2, 5
):"bb"
- Group 3 (positions
3, 6
):"cc"
- All groups form palindromes. Therefore,
"abcabc"
is a semi-palindrome.
- Group 1 (positions
Example 1:
Input: s = "abcac", k = 2
Output: 1
Explanation: Divide s
into "ab"
and "cac"
. "cac"
is already semi-palindrome. Change "ab"
to "aa"
, it becomes semi-palindrome with d = 1
.
Example 2:
Input: s = "abcdef", k = 2
Output: 2
Explanation: Divide s
into substrings "abc"
and "def"
. Each needs one change to become semi-palindrome.
Example 3:
Input: s = "aabbaa", k = 3
Output: 0
Explanation: Divide s
into substrings "aa"
, "bb"
and "aa"
. All are already semi-palindromes.
Constraints:
2 <= s.length <= 200
1 <= k <= s.length / 2
s
contains only lowercase English letters.
Solution
Python3
class Solution:
def minimumChanges(self, s: str, k: int) -> int:
N = len(s)
factors = defaultdict(lambda: [1])
for d in range(2, N):
for v in range(d + d, N + 1, d):
factors[v].append(d)
# to find the minimum cost to make s[i ... j] (both inclusive) "semi-palindrome"
@cache
def cost(start, end):
length = end - start + 1
if length <= 1: return inf
res = inf
for d in factors[length]:
subLen = length // d
changes = 0
for part in range(d):
for i in range(subLen // 2):
if s[start + part + i * d] != s[start + part + (subLen - i - 1) * d]:
changes += 1
res = min(res, changes)
return res
@cache
def go(i, k):
if k == 1: return cost(i, N - 1)
if i == N: return 0 if k == 0 else inf
res = inf
for j in range(i + 1, N):
res = min(res, go(j + 1, k - 1) + cost(i, j))
return res
return go(0, k)