#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> using namespace std; const int N=3e3+10; int n,K,tp; int f[2][(1<<13)+1][2][15]; int cnt[(1<<13)+1]; char ch[N]; int a[N]; struct Elysia{ int num,cnt; }d[(1<<13)+1]; bool cmp(Elysia x,Elysia y) { return x.cnt<y.cnt; } bool app[N][15]; int main() { scanf("%d %d %d",&n,&K,&tp); int tpp=(1<<K); scanf("%s",ch+1); for(int i=1;i<=n;i++) { a[i]=(int)(ch[i]-'a'+1); for(int j=1;j<=12;j++) app[i][j]=app[i-1][j]; app[i][a[i]]=1; } int p=0,nxt; for(int i=0;i<tpp;i++) d[i].cnt=d[i>>1].cnt+(i&1),d[i].num=i; sort(d,d+tpp,cmp); for(int i=0;i<=n;i++) { nxt=p^1; for(int s=0;s<tpp;s++) { if(d[s].cnt>i) break; if(f[nxt][s][0][a[i]]<f[p][s][1][a[i]]) f[nxt][s][0][a[i]]=f[p][s][1][a[i]]; // else if(f[nxt][s][0][a[i]]==f[p][s][1][a[i]]&&ss[nxt][s][0][a[i]]>ss[p][s][1][a[i]]) // ss[nxt][s][0][a[i]]=ss[p][s][1][a[i]]; if(!(s&(1<<a[i+1]-1))) { if(a[i+1]!=a[i]) { if(f[nxt][s|(1<<a[i]-1)][1][a[i+1]]<f[p][s][1][a[i]]+1) f[nxt][s|(1<<a[i]-1)][1][a[i+1]]=f[p][s][1][a[i]]+1; // else if(f[nxt][s|(1<<a[i]-1)][1][a[i+1]]==f[p][s][1][a[i]]+1&&ss[nxt][s|(1<<a[i]-1)][1][a[i+1]]>ss[p][s][1][a[i]]+ch[i+1]) // ss[nxt][s|(1<<a[i]-1)][1][a[i+1]]=ss[p][s][1][a[i]]+ch[i+1]; } else { if(f[nxt][s][1][a[i+1]]<f[p][s][1][a[i]]+1) f[nxt][s][1][a[i+1]]=f[p][s][1][a[i]]+1; // else if(f[nxt][s][1][a[i+1]]==f[p][s][1][a[i]]+1&&ss[nxt][s][1][a[i+1]]>ss[p][s][1][a[i]]+ch[i+1]) // ss[nxt][s][1][a[i+1]]=ss[p][s][1][a[i]]+ch[i+1]; } } for(int j=1;j<=12;j++) { if((s&(1<<j-1))&&app[i][j]) continue; if(f[nxt][s][0][j]<f[p][s][0][j]) f[nxt][s][0][j]=f[p][s][0][j]; // else if(f[nxt][s][0][j]==f[p][s][0][j]&&ss[nxt][s][0][j]>ss[p][s][0][j]) // ss[nxt][s][0][j]=ss[p][s][0][j]; if(!(s&(1<<a[i+1]-1))) { if(a[i+1]==j) { if(f[nxt][s][1][a[i+1]]<f[p][s][0][j]+1) f[nxt][s][1][a[i+1]]=f[p][s][0][j]+1; // else if(f[nxt][s][1][a[i+1]]==f[p][s][0][j]&&ss[nxt][s][1][a[i+1]]>ss[p][s][0][j]+ch[i+1]) // ss[nxt][s][1][a[i+1]]=ss[p][s][0][j]+ch[i+1]; } else { if(f[nxt][s|(1<<j-1)][1][a[i+1]]<f[p][s][0][j]+1) f[nxt][s|(1<<j-1)][1][a[i+1]]=f[p][s][0][j]+1; // else if(f[nxt][s|(1<<j-1)][1][a[i+1]]==f[p][s][0][j]+1&&ss[nxt][s|(1<<j-1)][1][a[i+1]]>ss[p][s][0][j]+ch[i+1]) // ss[nxt][s|(1<<j-1)][1][a[i+1]]=ss[p][s][0][j]+ch[i+1]; } } } } p^=1; } int ans=0; string rans=" "; for(int s=0;s<tpp;s++) for(int j=1;j<=12;j++) { if(f[p^1][s][0][j]>ans) ans=f[p^1][s][0][j]; // else if(f[p^1][s][0][j]==ans&&rans>ss[p^1][s][0][j]) // rans=ss[p^1][s][0][j]; if(f[p^1][s][1][j]>ans) ans=f[p^1][s][1][j]; // else if(ans==f[p^1][s][1][j]&&rans>ss[p^1][s][1][j]) // rans=ss[p^1][s][1][j]; } printf("%d\n",ans); if(tp) cout<<rans<<endl; return 0; }