fork download
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. int compute(int l, int r, string s, char c){
  7. if(l==r) return s[l] == c ? 0 : 1;
  8. int mid = l+(r-l)/2;
  9. int cnt1=0,cnt2=0;
  10. for(int i=l; i<=mid; i++){
  11. if(s[i] != c) cnt1++;
  12. }
  13. for(int i=mid+1; i<=r; i++){
  14. if(s[i] != c) cnt2++;
  15. }
  16. return min(compute(mid+1,r,s,c+1)+cnt1,compute(l,mid,s,c+1)+cnt2);
  17. }
  18.  
  19. int main(){
  20. ios_base::sync_with_stdio(false);
  21. cin.tie(NULL);
  22. int t,n;
  23. string s;
  24. cin>>t;
  25. while(t-- > 0){
  26. cin>>n>>s;
  27. cout<<compute(0,n-1,s,'a')<<"\n";
  28. }
  29. return 0;
  30. }
Success #stdin #stdout 0s 4364KB
stdin
6
8
bbdcaaaa
8
asdfghjk
8
ceaaaabb
8
bbaaddcc
1
z
2
ac
stdout
0
7
4
5
1
1