1278. Palindrome Partitioning III¶
题目信息¶
- 题号:
1278
- 难度:
Hard
- 主题:
字符串、区间动态规划、分段
- 原题:
- 重点:
把整个字符串划分为恰好
k个连续非空子串,可修改字符并最小化使每段都成为回文串的修改次数
题目重述¶
给定只包含小写英文字母的字符串 s 和整数 k。需要按原顺序把整个字符串划分成恰好 k 个连续且非空的子串。
可以把任意位置的字符修改为其他小写字母。请返回使每个分段都成为回文串所需的最少字符修改次数。
1 <= k <= s.length <= 100。
自建示例¶
整个字符串作为一段时只需修复不匹配字符对:
输入:s = "abca", k = 1
输出:1
解释:首尾 a 已匹配,只需把中间的 b 或 c 修改为另一个字符即可得到回文串。
每个字符单独成段时无需修改:
输入:s = "code", k = 4
输出:0
解释:四个长度为一的子串本身都是回文串。