题目重点：将最多删1个、2个和K个字符合并为同题变体，说明固定小K与一般K的复杂度区别。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 字符大小写敏感，删除不改变剩余字符顺序，允许少于K次；空串为回文，K非负。只返回是否可行，不要求输出删除位置。
- 这里是删除字符而非交换、替换或删除连续块。示例Python按Unicode码点，若输入要求grapheme需先分词。
- 不需删除的标准验证变体可先忽略非ASCII字母数字并大小写不敏感，用is_alnum_palindrome_ascii；这不等于删除预算中的原字符比较，预处理合同不同。
解题路线
- 双指针从两端跳过相同字符；遇到冲突时任何回文结果必须删除左端或右端至少一个。分别递归剩余区间并减少budget，两支取OR；budget0时冲突立即失败。
- K=1时只需检查删除左端或右端后的两个子串，K=2至多再分两层。不能贪心总删左端，例如不同输入可能只有删右端可行。缓存(left,right,budget)避免同状态重复，但不能据此凭空说一般K必为O(nK)。
- 一般K用最少删除区间DP：相等取内区间，不等取1+min(删左,删右)。长度1为0，空区间为0；最终minDeletes≤K。
- 滚动一行dp时left倒序、right正序，旧dp[right]代表下一行，dp[right-1]是本行，diagonal保存旧内区间。覆盖顺序错误会把同一行结果当旧行。
- 若需输出删除位置，保存二维选择或进行带检查点的重构；一行长度值本身不能直接恢复完整路径。大输入递归可能遇Python栈深限制，一般K优先迭代DP。
- 标准忽略标点的验证以两指针跳过非法字符，比较ASCII字符lower；只求合法性O(N)时间/O(1)状态，不生成过滤副本。删除K变体仍对原text大小写敏感，不共用未声明normalize。
手动走一遍
abca最多删1可行：删b或c。abc最多删1不行，最多删2可行。abcbda的最少删除是1（删d得到abcba）；在每次冲突固定删左端不能证明正确，应枚举两端候选。 标准验证A man, a plan, a canal: Panama为True，但大小写敏感且预算0的原字符删除合同不能当作同一答案。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
from functools import lru_cache
def can_make_palindrome(text, k):
"""At most k deleted characters, case sensitive. Memoized branching baseline."""
if k < 0: raise ValueError('nonnegative budget')
@lru_cache(None)
def solve(left, right, budget):
while left < right and text[left] == text[right]:
left += 1; right -= 1
if left >= right: return True
if budget == 0: return False
return solve(left+1, right, budget-1) or solve(left, right-1, budget-1)
return solve(0, len(text)-1, k)
def minimum_deletions(text):
"""O(n^2) time, O(n) auxiliary space rolling interval DP."""
n=len(text);dp=[0]*n
for left in range(n-2,-1,-1):
diagonal=0
for right in range(left+1,n):
old=dp[right]
dp[right]=diagonal if text[left]==text[right] else 1+min(dp[right],dp[right-1])
diagonal=old
return dp[-1] if n else 0
def is_alnum_palindrome_ascii(text):
"""No deletions budget; ignore non-ASCII-alphanumeric, compare case-insensitive."""
def allowed(ch):return 'a'<=ch<='z' or 'A'<=ch<='Z' or '0'<=ch<='9'
left=0;right=len(text)-1
while left<right:
if not allowed(text[left]):left+=1;continue
if not allowed(text[right]):right-=1;continue
if text[left].lower()!=text[right].lower():return False
left+=1;right-=1
return True
复杂度
固定小K的分支基线保守O(n·2^K)时间、O(K)递归深度加缓存；K=1或2可视为O(n)。一般DP O(n²)时间/O(n)辅助空间；不能把任意K的双指针递归直接标O(nK)。
易错点与追问
容易失分的边界
- 最多K不等于必须正好K，已经回文可以不删。
- 用最长回文子串长度判断删除数错误：删除保留的是子序列。
继续深挖
- 若返回一个最少删除后的回文，怎样记录tie政策与重构选择？
- K非常小而n很大时，为什么指数只依赖K的分支可能比全二维DP合适？
