UVa 11552 - Fewest Flops

//\\__ hr1212 __//\\

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef map<int,int> mi;

#define si(a) scanf("%d",&a)
#define sii(a,b) scanf("%d %d",&a,&b)
#define siii(a,b,c) scanf("%d %d %d",&a,&b,&c)
#define pi(a) printf("%d\n",a)
#define nl printf("\n");
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define f(i,a,b) for(i=a;i<b;i++)
#define rf(i,a,b) for(i=a;i>=b;i--)
#define clr(x,a) memset(x,a,sizeof(x))
#define MAX 100010
#define MOD 1000000007

int n,m,a[30];
vi v[MAX];

int dp[MAX][28];

int solve(int i,int ed){
    int j,k;
    if(i>=n)
        return dp[i][ed]=0;
    if(dp[i][ed]!=-1)
        return dp[i][ed];
    int z=1e9;
    if(v[i].size()==1){
        if(ed==v[i][0])
            z=solve(i+1,v[i][0]);
        else
            z=solve(i+1,v[i][0])+1;
    }
    else{
    for(j=0;j<v[i].size();j++){
        for(k=0;k<v[i].size();k++){
            if(j==k)
                continue;
            if(ed==v[i][j])
                z=min(z,solve(i+1,v[i][k])+(int)v[i].size()-1);
            else
                z=min(z,solve(i+1,v[i][k])+(int)v[i].size());
        }
    }
    }
    return dp[i][ed]=z;
}

int main(){
    int r,k,i,c=0,x=0,y=0,j,t,l,z,x1=0,y1=0;
    ll ans=0;string p;

    si(t);
    while(t--){
        si(k);
        cin>>p;
        n=p.size();
        for(i=0;i<n;i+=k){
            clr(a,0);
            f(j,i,i+k){
                a[p[j]-'a']++;
            }
            f(j,0,26){
                if(a[j]!=0)
                    v[i/k].pb(j+1);
            }
        }
        n=n/k;
        clr(dp,-1);
        cout<<solve(0,0)<<endl;
        f(i,0,1000)
            v[i].clear();
    }

    return 0;
}