题解 | 小红的双生串

贪心统计法 (Optimal Greedy)

逻辑原理：

由于双生串的前半部分必须是同一个字符，后半部分也必须是同一个字符，我们可以独立地处理这两个部分：

1. 前半部分：统计前n/2个字符中出现频率最高的字符。假设最高频率为maxFreq1，那么前半部分最少修改次数就是n/2 - maxFreq1
2. 后半部分：统计后n/2个字符中出现频率最高的字符。假设最高频率为maxFreq2，那么后半部分最少修改次数就是n/2 - maxFreq2
3. 总计：将两部分的最小修改次数相加即可。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 贪心统计
        String line = in.nextLine();
        int n = line.length();
        int half = n / 2;

        // 处理前半部分
        int[] freq1 = new int[26];
        int maxFreq1 = 0;
        for (int i = 0; i < half; i++) {
            int idx = line.charAt(i) - 'a';
            freq1[idx]++;
            maxFreq1 = Math.max(maxFreq1, freq1[idx]);
        }

        // 处理后半部分
        int[] freq2 = new int[26];
        int maxFreq2 = 0;
        for (int i = half; i < n; i++) {
            int idx = line.charAt(i) - 'a';
            freq2[idx]++;
            maxFreq2 = Math.max(maxFreq2, freq2[idx]);
        }

        // 最小修改次数 = 总长度 - 两部分分别保留的最大相同字符数
        int minChange = n - maxFreq1 - maxFreq2;
        System.out.println(minChange);
    }
}