考虑偶数的回文子串最简单的情况就是两个相同的字符,只要把相邻且相同的字符只保留一个就不会出现偶数回文串了,因为更长的回文串中间那两个字符肯定也得相等才行。
直接计算相邻字符的数量即可,相邻的总数减一就是需要去除的。时间复杂度O(n)
小美有一个长为n的字符串s,他希望删除尽可能少的字符,使得字符串不含长度为偶数的回文子串
他想知道最少要删除几个字符。
第一行一个正整数n(≤105),表示s的长度
接下来一行一个长为n的字符串s
一个整数,表示答案
输入
5
aaabc
输出
2
说明
删除变为abc
输入
1
e
输出
0