1000ms

Difficulty: 3

所属公司 : 美团

时间 :2024年3月23日

算法与标签>贪心算法

会员或题库专享

请先，开通会员或购买题库美团机考编程题库，可解锁完整内容。

购买美团机考编程题库开通会员

会员专享

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

购买题库开通会员

题目思路

考虑偶数的回文子串最简单的情况就是两个相同的字符，只要把相邻且相同的字符只保留一个就不会出现偶数回文串了，因为更长的回文串中间那两个字符肯定也得相等才行。

直接计算相邻字符的数量即可，相邻的总数减一就是需要去除的。时间复杂度 $O(n)$

代码

题目描述

小美有一个长为 $n$ 的字符串 $s$ ，他希望删除尽可能少的字符，使得字符串不含长度为偶数的回文子串

他想知道最少要删除几个字符。