算法

(构造) $O(n)$

结论：这样的串只有两种形式，要么全部都是相同的字符串，要么只有两种字符串交替出现。（自证）

实现方法：只需要分两种情况：第一种全部相同的字符，只需要扫一遍统计一下出现最多的字符是多少，并且把剩下的字符全部修改成该字符就可以完全。第二种情况，考虑奇数位置上出现最多的字符和偶数位置上出现最多的字符，将剩下的字符全部修改成这两种字符，最后对于这两种情况取一个最优的答案作为最终的答案。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        string s;
        cin >> s;
        int n = s.size();
        vector<int> cnt1(30, 0);
        for (int i = 0; i < n; ++i) cnt1[s[i] - 'a']++;
        int t1 = cnt1[0];
        for (int i = 1; i < cnt1.size(); ++i) {
            t1 = max(t1, cnt1[i]);
        }
        int res1 = n - t1;

        vector<int> cnt2(30, 0);
        for (int i = 0; i < n; i += 2) cnt2[s[i] - 'a']++;
        int t2 = cnt2[0];
        for (int i = 1; i < cnt2.size(); ++i) {
            t2 = max(t2, cnt2[i]);
        }
        int res2 = (n & 1 == 0) ? n / 2 : (n + 1) / 2 - t2;

        vector<int> cnt3(30, 0);
        for (int i = 1; i < n; i += 2) cnt3[s[i] - 'a']++;
        int t3 = cnt3[0];
        for (int i = 0; i < cnt3.size(); ++i) {
            t3 = max(t3, cnt3[i]);
        }
        int res3 = n / 2 - t3;

        cout << min(res1, res2 + res3) << '\n';
    }

    return 0;
}