题目描述

难度分:$1500$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的字符串$s$，只包含小写英文字母。

你需要把$s$变成长为偶数的交替字符串（所有偶数下标字母都一样，所奇数下标字母都一样）。

有两种操作：

1. 删除$s[i]$，该操作至多执行一次。
2. 把$s[i]$改成其他字母。

输出最小操作次数。

输入样例

10
1
a
2
ca
3
aab
5
ababa
6
acdada
9
ejibmyyju
6
bbccbc
6
abacba
5
bcbca
5
dcbdb

输出样例

1
0
1
1
2
6
2
3
1
1

算法

枚举

一、如果$s$的长度为偶数

不需要进行删除操作，只要进行修改操作。那就用两个长度为$26$的数组$odd$、$even$，分别用来统计奇数位置和偶数位置的字母频数，利用$odd$和$even$得到奇数位置和偶数位置出现最多的字母频数$mode_1$和$mode_2$，答案就是$n-mode_1-mode_2$。

二、如果$s$的长度为奇数

就必须要进行一次删除操作。我们枚举待删除的位置$i$，删除掉$i$之后：

1. 前缀$[1,i)$的奇数位置就要和后缀$(i,n]$的偶数位置组合起来，形成新串的奇数位置。
2. 前缀$[1,i)$的偶数位置就要和后缀$(i,n]$的奇数位置组合起来，形成新串的偶数位置。

准备四个长度为$26$的频数数组$po$、$pe$、$so$、$se$分别用来维护原串前缀$[1,i)$上奇数位置的字母频数、偶数位置的字母频数、原串$(i,n]$上奇数位置的字母频数、偶数位置的字母频数。双重循环枚举新串奇数位置和偶数位置分别为$c_0$和$c_1$，在遍历待删除位置$i$的时候维护这四个数组，根据$1$和$2$两种规则进行组合，计算出需要操作多少次，取最小值即可得到最终答案。

稍微细说一下对于给定的$c_0$和$c_1$，怎么计算操作次数？我们需要一个函数$get(l,r)$可以获得$[l,r]$内奇数的数目（偶数也可以，这个推导一下就可以$O(1)$计算出来），那么此时$[1,i)$中偶数位置就会和$(i,n]$中的奇数位置组合成新串的偶数位置，修改次数为$s_0=i-1-get(1,i-1)-pe[c_0]+get(i,n)-so[c_0]$，即前缀偶数位置上不是$c_0$的位置个数$+$后缀奇数位置上不是$c_0$的位置个数。

同理，对于$c_1$我们也可以得到修改次数$s_1=get(1,i-1)-po[c_1]+n-i-get(i+1,n)-se[c_1]$。最后还需要加上一个删除操作，总操作次数为$1+s_0+s_1$，维护最小值。

复杂度分析

时间复杂度

分析一下最差情况，在最差情况下，枚举被删除的字符$i \in [1,n]$时间复杂度为$O(n)$。而对于每个$i$，需要枚举新串的奇数位置和偶数位置分别为什么字母，时间复杂度为$O(\Sigma^2)$，其中$\Sigma=26$为字符集的大小。所以整个算法的时间复杂度为$O(n\Sigma^2)$。

空间复杂度

空间消耗主要在于几个字母统计频数表，每个频数表的长度都是$O(\Sigma)$，这也是整个算法的额外空间复杂度。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int T, n, po[26], pe[26], so[26], se[26];
char s[N];

int pre(int x) {
    return (x + 1) >> 1;
}

int countOdds(int low, int high) {
    return pre(high) - pre(low - 1);    // 计算[low,high]中有多少个奇数
}

void solve() {
    if(n&1) {
        for(int i = 0; i < 26; i++) {
            po[i] = pe[i] = so[i] = se[i] = 0;
        }
        // 此时有个字母是要删掉的
        for(int i = 1; i <= n; i++) {
            if(i&1) {
                so[s[i] - 'a']++;
            }else {
                se[s[i] - 'a']++;
            }
        }
        // 枚举要删除的字母
        int ans = n + 1;
        for(int i = 1; i <= n; i++) {
            if(i&1) {
                so[s[i] - 'a']--;
            }else {
                se[s[i] - 'a']--;
            }
            for(char c0 = 'a'; c0 <= 'z'; c0++) {
                for(char c1 = 'a'; c1 <= 'z'; c1++) {
                    // 偶数位置c0，奇数位置c1
                    int eop = i - 1 - countOdds(1, i - 1) - pe[c0 - 'a'] + countOdds(i + 1, n) - so[c0 - 'a'];
                    int oop = countOdds(1, i - 1) - po[c1 - 'a'] + n - i - countOdds(i + 1, n) - se[c1 - 'a'];
                    ans = min(ans, eop + oop + 1);
                }
            }
            if(i&1) {
                po[s[i] - 'a']++;
            }else {
                pe[s[i] - 'a']++;
            }
        }
        printf("%d\n", ans);
    }else {
        vector<int> odd(26), even(26);
        // 此时不能删字母
        int mode1 = 0, mode2 = 0;
        for(int i = 1; i <= n; i += 2) {
            odd[s[i] - 'a']++;
            mode1 = max(mode1, odd[s[i] - 'a']);
        }
        for(int i = 2; i <= n; i += 2) {
            even[s[i] - 'a']++;
            mode2 = max(mode2, even[s[i] - 'a']);
        }
        printf("%d\n", n - mode1  - mode2);
    }
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        scanf("%s", s + 1);
        solve();
    }
    return 0;
}