小红的回文子串（B组）

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

小红拿到了一个字符串，她可以操作最多1次：修改任意一个字符。
小红希望操作结束后，长度为3的回文连续子串的数量尽可能多。请你求出这个数量。

输入描述:

一个仅包含小写字母的字符串。长度不超过100。

输出描述:

一个整数，代表操作结束后，长度为3的回文连续子串的数量的最大值。

示例1

输入

复制abcde

abcde

输出

复制1

1

说明

将第二个字符修改为'd'即可，这样字符串变成"adcde"，共包含1个长度为3的回文子串。

import java.util.Scanner;

public class Main {

    // 计算字符串 s 中三字符回文子串的个数。
    public static int countThreePalindrome(String s) {
        int count = 0;
        for (int i = 1; i < s.length() - 1; ++i) {
            if (s.charAt(i - 1) == s.charAt(i + 1)) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        int ans = countThreePalindrome(s); // 不修改的初始回文数

        // 根据题目要求，s 长度最大为 100. 因此可以承受 O(26 * n^2) 的复杂度。
        for (int i = 0; i < s.length(); ++i) {
            for (char ch = 'a'; ch <= 'z'; ++ch) { // 枚举所有可能的字符
                StringBuilder modified = new StringBuilder(s);
                modified.setCharAt(i, ch);    // 替换当前位置的字符为 ch
                ans = Math.max(ans, countThreePalindrome(modified.toString())); // 维护替换后回文的最大数量
            }
        }

        System.out.println(ans); // 输出回文的最大数量
        scanner.close();
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        //长度为3只有两种情况 aba 和 aaa 也就是说中间那个数其实不重要 首尾决定了是否是回文串
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String s = bf.readLine();
        long res = 0;
        for (int i = 0; i + 2 < s.length(); i++) {
            if(s.charAt(i) == s.charAt(i+2)) res++;
        }

        for (int i = 2; i + 2 < s.length(); i++) {
            //最优情况 因为操作是能修改一次 只要存在这种情况直接修改 在原res基础上算上2的贡献度
            if(s.charAt(i) != s.charAt(i + 2) && s.charAt(i) != s.charAt(i - 2) && s.charAt(i - 2) == s.charAt(i + 2)){
                System.out.println(res+2);
                return;
            }
        }

        for (int i = 2; i < s.length(); i++) {
            //改成等于前面的
            if(s.charAt(i) != s.charAt(i - 2) && (i + 2 > s.length() || s.charAt(i + 2) != s.charAt(i - 2))) {
                System.out.println(res+1);
                return;
            }
        }

        for (int i = 0; i + 2 < s.length(); i++) {
            //改成等于后面的
            if(s.charAt(i) != s.charAt(i + 2) && (i - 2 < 0 || s.charAt(i + 2) != s.charAt(i - 2))) {
                System.out.println(res+1);
                return;
            }
        }
        System.out.println(res);
    }
}