1000ms

Difficulty: 4

所属公司 : 拼多多

时间 :2023年8月22日

算法与标签>思维

会员或题库专享

请先，开通会员或购买题库拼多多机考题库，可解锁完整内容。

购买拼多多机考题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（拼多多机考题库），可解锁完整内容。

购买题库开通会员

思路：思维

首先考虑将 $s[i]$ 与 $s[j]$ 修改为相同，满足 $0\leq i, j\leq n-1, i+j=n-1$ 。

如果修改了 $cnt$ 次：

$cnt > k$ ，则必然无法修改为回文串。
$cnt == k$ ，则恰好可以修改为回文串
$cnt < k$ 但是 $n$ 是奇数，那么多的 $k - cnt$ 次都用来修改最中间的字符即可

题目内容

小红有一个字符串 $s$ 。

现在小红给这个串恰好 $k$ 次修改，问修改后的串是否可能是回文串？需要保证修改一个字符后，修改前后的字符不同。