题目描述
难度分:1500
输入T(≤104)表示T组数据。所有数据的n之和≤2×105。
每组数据输入n(1≤n≤2×105)和长为n的字符串s,只包含小写英文字母。
你需要把s变成长为偶数的交替字符串(所有偶数下标字母都一样,所奇数下标字母都一样)。
有两种操作:
- 删除s[i],该操作至多执行一次。
- 把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得到奇数位置和偶数位置出现最多的字母频数mode1和mode2,答案就是n−mode1−mode2。
二、如果s的长度为奇数
就必须要进行一次删除操作。我们枚举待删除的位置i,删除掉i之后:
- 前缀[1,i)的奇数位置就要和后缀(i,n]的偶数位置组合起来,形成新串的奇数位置。
- 前缀[1,i)的偶数位置就要和后缀(i,n]的奇数位置组合起来,形成新串的偶数位置。
准备四个长度为26的频数数组po、pe、so、se分别用来维护原串前缀[1,i)上奇数位置的字母频数、偶数位置的字母频数、原串(i,n]上奇数位置的字母频数、偶数位置的字母频数。双重循环枚举新串奇数位置和偶数位置分别为c0和c1,在遍历待删除位置i的时候维护这四个数组,根据1和2两种规则进行组合,计算出需要操作多少次,取最小值即可得到最终答案。
稍微细说一下对于给定的c0和c1,怎么计算操作次数?我们需要一个函数get(l,r)可以获得[l,r]内奇数的数目(偶数也可以,这个推导一下就可以O(1)计算出来),那么此时[1,i)中偶数位置就会和(i,n]中的奇数位置组合成新串的偶数位置,修改次数为s0=i−1−get(1,i−1)−pe[c0]+get(i,n)−so[c0],即前缀偶数位置上不是c0的位置个数+后缀奇数位置上不是c0的位置个数。
同理,对于c1我们也可以得到修改次数s1=get(1,i−1)−po[c1]+n−i−get(i+1,n)−se[c1]。最后还需要加上一个删除操作,总操作次数为1+s0+s1,维护最小值。
复杂度分析
时间复杂度
分析一下最差情况,在最差情况下,枚举被删除的字符i∈[1,n]时间复杂度为O(n)。而对于每个i,需要枚举新串的奇数位置和偶数位置分别为什么字母,时间复杂度为O(Σ2),其中Σ=26为字符集的大小。所以整个算法的时间复杂度为O(nΣ2)。
空间复杂度
空间消耗主要在于几个字母统计频数表,每个频数表的长度都是O(Σ),这也是整个算法的额外空间复杂度。
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;
}