LeetCode 题解工作台
得到 K 个半回文串的最少修改次数
给你一个字符串 s 和一个整数 k ，请你将 s 分成 k 个 子字符串 ，使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。 请你返回一个整数，表示需要修改的 最少 字符数目。 注意： 如果一个字符串从左往右和从右往左读是一样的，那么它是一个 回文串 。 如果长度为 len 的字符串存在…
3
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
class Solution: def minimumChanges(self, s: str, k: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个字符串 s 和一个整数 k ，请你将 s 分成 k 个 子字符串 ，使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。
请你返回一个整数，表示需要修改的 最少 字符数目。
注意：
- 如果一个字符串从左往右和从右往左读是一样的，那么它是一个 回文串 。
- 如果长度为
len的字符串存在一个满足1 <= d < len的正整数d，len % d == 0成立且所有对d做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 ，那么我们说这个字符串是 半回文串 。比方说"aa"，"aba"，"adbgad"和"abab"都是 半回文串 ，而"a"，"ab"和"abca"不是。 - 子字符串 指的是一个字符串中一段连续的字符序列。
示例 1：
输入：s = "abcac", k = 2 输出：1 解释：我们可以将 s 分成子字符串 "ab" 和 "cac" 。子字符串 "cac" 已经是半回文串。如果我们将 "ab" 变成 "aa" ，它也会变成一个 d = 1 的半回文串。 该方案是将 s 分成 2 个子字符串的前提下，得到 2 个半回文子字符串需要的最少修改次数。所以答案为 1 。
示例 2:
输入：s = "abcdef", k = 2 输出：2 解释：我们可以将 s 分成子字符串 "abc" 和 "def" 。子字符串 "abc" 和 "def" 都需要修改一个字符得到半回文串，所以我们总共需要 2 次字符修改使所有子字符串变成半回文串。 该方案是将 s 分成 2 个子字符串的前提下，得到 2 个半回文子字符串需要的最少修改次数。所以答案为 2 。
示例 3：
输入：s = "aabbaa", k = 3 输出：0 解释：我们可以将 s 分成子字符串 "aa" ，"bb" 和 "aa" 。 字符串 "aa" 和 "bb" 都已经是半回文串了。所以答案为 0 。
提示：
2 <= s.length <= 2001 <= k <= s.length / 2s只包含小写英文字母。
解题思路
方法一
class Solution:
def minimumChanges(self, s: str, k: int) -> int:
n = len(s)
g = [[inf] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(i, n + 1):
m = j - i + 1
for d in range(1, m):
if m % d == 0:
cnt = 0
for l in range(m):
r = (m // d - 1 - l // d) * d + l % d
if l >= r:
break
if s[i - 1 + l] != s[i - 1 + r]:
cnt += 1
g[i][j] = min(g[i][j], cnt)
f = [[inf] * (k + 1) for _ in range(n + 1)]
f[0][0] = 0
for i in range(1, n + 1):
for j in range(1, k + 1):
for h in range(i - 1):
f[i][j] = min(f[i][j], f[h][j - 1] + g[h + 1][i])
return f[n][k]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to optimize the problem using dynamic programming and two-pointer techniques.
- question_mark
Check how well the candidate understands the state transition DP approach and its application to partitioning problems.
- question_mark
Evaluate their understanding of optimizing substring validation to minimize time complexity.
常见陷阱
外企场景- error
Misunderstanding the concept of semi-palindromes and overcomplicating substring validation.
- error
Failing to optimize the validation process, resulting in a brute force solution with high time complexity.
- error
Incorrectly managing the transitions between substring partitions, leading to higher than necessary letter changes.
进阶变体
外企场景- arrow_right_alt
Adjusting the value of k to test different partition sizes and their effect on time complexity.
- arrow_right_alt
Varying the types of allowed transformations to include other string operations beyond letter changes.
- arrow_right_alt
Increasing the length of the string to test the scalability of the solution.