#include<cstdio> #include<algorithm> #include<ctype.h> #include<cstring> #include<iostream> #include<vector> #include<queue> #include<ctime> #include<cmath> #include<queue> #include<map> #include<set> #include<unordered_map> #include<stack> #define pr pair<int,int> #define eps 1e-8 #define db double using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-')f=-1; ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); } return x*f; } int n,k,ans; char s[3005]; void solve1() { int dp[2][(1<<12)+5][13]; memset(dp,0,sizeof(dp)); for(int now=1,i=1; i<=n; i++,now^=1) { for(int j=0; j<(1<<k); j++) for(int l=0; l<k; l++) dp[now][j][l]=0; for(int j=1; j<(1<<k); j++) { for(int l=0; l<k; l++) { if(!((j>>l)&1)) continue; if(s[i]-'a'==l) { dp[now][j][l]=dp[now^1][j][l]+1; for(int qwq=0; qwq<k; qwq++) if(qwq!=l&&((j>>qwq)&1)) dp[now][j][l]=max(dp[now][j][l],dp[now^1][j^(1<<l)][qwq]+1); } else dp[now][j][l]=dp[now^1][j][l]; } } if(i==n) for(int j=1; j<(1<<k); j++) for(int l=0; l<k; l++) ans=max(ans,dp[now][j][l]); } printf("%d\n",ans); } struct Node { int x,y,z; Node(int x=0,int y=0,int z=0):x(x),y(y),z(z) {} }; int dp[205][(1<<12)+5][13]; Node pre[205][(1<<12)+5][13]; void solve2() { int ans=0,curx,cury,curz; for(int i=1; i<=n; i++) { for(int j=1; j<(1<<k); j++) { for(int l=0; l<k; l++) { if(!((j>>l)&1)) continue; if(s[i]-'a'==l) { dp[i][j][l]=dp[i-1][j][l]+1; pre[i][j][l]=Node(i-1,j,l); for(int qwq=0; qwq<k; qwq++) if(qwq!=l&&((j>>qwq)&1)) { if(dp[i-1][j^(1<<l)][qwq]+1>dp[i][j][l]||(dp[i-1][j^(1<<l)][qwq]+1==dp[i][j][l]&&pre[i][j][l].z>qwq)) dp[i][j][l]=dp[i-1][j^(1<<l)][qwq]+1,pre[i][j][l]=Node(i-1,j^(1<<l),qwq); } } else dp[i][j][l]=dp[i-1][j][l],pre[i][j][l]=Node(i-1,j,l); } } if(i==n) for(int j=1; j<(1<<k); j++) for(int l=0; l<k; l++) { if(ans<dp[n][j][l]||(ans==dp[n][j][l]&&curz>l)) ans=dp[n][j][l],curx=n,cury=j,curz=l; } } printf("%d\n",ans); vector<int>ret; while(curx) { if(s[curx]-'a'==curz) ret.push_back(curz); Node awa=pre[curx][cury][curz]; curx=awa.x,cury=awa.y,curz=awa.z; } reverse(ret.begin(),ret.end()); for(vector<int>::iterator v=ret.begin(); v!=ret.end(); v++) putchar('a'+(*v)); return; } int main() { // freopen("seq4.in","r",stdin); // freopen("seq4.out","w",stdout); n=read(),k=read(); int ty=read(); scanf("%s",s+1); if(ty==0) solve1(); else solve2(); // fclose(stdin); // fclose(stdout); return 0; }