一种分治的思想,看每次的左右区间,找一个需要更改小的进行更改,然后对另一个区间进行继续往下分治的更改。
#include<cstdio>
#include<iostream>
using namespace std;
int T,n;
char s[200005];
int solve(int l,int r,char c){
if(l==r){
if(s[l]==c) return 0;
return 1;
}
int cnt=0,tot=0;
int mid=(l+r)>>1;
for(int i=l;i<=mid;i++){
if(s[i]!=c) cnt++;
}
for(int i=mid+1;i<=r;i++){
if(s[i]!=c) tot++;
}
cnt+=solve(mid+1,r,(char)(c+1));
tot+=solve(l,mid,(char)(c+1));
return min(cnt,tot);
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
scanf("%s",s+1);
printf("%d\n",solve(1,n,'a'));
}
return 0;
}