题目思路

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

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

代码

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String s = scanner.next();
        char ch = ' ';
        int ans = 0;
        for (int i = 0; i < n; i++) {
            char v = s.charAt(i);
            if (v == ch) {
                ans++;
            }
            ch = v;
        }
        System.out.println(ans);
    }
}

C++

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    char ch = ' ';
    int ans = 0;
    for (int i = 0; i < n; i++) {
        char v = s[i];
        if (v == ch) {
            ans++;
        }
        ch = v;
    }
    cout << ans << endl;
    return 0;
}

Python

n = int(input())
s = input()
ch, ans = -1, 0
for v in s:
    if v == ch:
        ans += 1
    ch = v
print(ans)

会员可通过查看《已通过》的提交记录来查看其他语言哦~

题目描述

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

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

输入描述

第一行一个正整数$n(\le10^5)$，表示$s$的长度

接下来一行一个长为$n$的字符串$s$

输出描述

一个整数，表示答案

样例

输入

5
aaabc

输出

2

说明

删除变为abc

输入

1
e

输出

0