以下将状态 \(K\)，\(E\)，\(Y\) 用数字0,1,2表示。
考虑 \(dp\)
我们设 \(dp[a][b][c][d]\) 表示 \(K\) 用了 \(a\) 次，\(E\) 用了 \(b\) 次，\(Y\) 用了 \(c\) 次，总共交换了 \(d\) 次，
前缀和 $sum[i][j] $表示到第 \(j\) 位有几个字母 \(i\)
记录一个 \(loc[i][j]\)表示第 \(j\) 个字母 \(i\) 在哪里
那么对于 \(dp[a][b][c][d]\)，以再选一个 \(a\) 为例，转移应为：
\[dp[a+1][b][c][d+max(0,sum[1][loc[0][a+1]+1]-b) max(0,sum[2][loc[0][a+1]+1]-c)]\\+=dp[a][b][c][d] \]ACcode
#include<bits/stdc艹.h>
using namespace std;
#define int long long
char s[40];
int n,num[3],sum[3][32],loc[3][32],dp[32][32][32][910],ans=0,O=0;
signed main(){
cin>>s+1>>n;
int len=strlen(s+1);
for(int i=1;i<=len;i++){
int m;
if(s[i]=='K'){
m=0;
}
else if(s[i]=='E'){
m=1;
}
else{
m=2;
}
sum[0][i]+=sum[0][i-1];
sum[1][i]+=sum[1][i-1];
sum[2][i]+=sum[2][i-1];
sum[m][i]++;
num[m]++;
loc[m][num[m]]=i;
}
dp[0][0][0][0]=1;
for(int k=0;k<=num[0];k++){
for(int e=0;e<=num[1];e++){
for(int y=0;y<=num[2];y++){
for(int step=0;step<=n&&step<=900;step++){
dp[k+1][e][y][step+max(O,sum[1][loc[0][k+1]]-e)+max(O,sum[2][loc[0][k+1]]-y)]+=dp[k][e][y][step];
dp[k][e+1][y][step+max(O,sum[0][loc[1][e+1]]-k)+max(O,sum[2][loc[1][e+1]]-y)]+=dp[k][e][y][step];
dp[k][e][y+1][step+max(O,sum[0][loc[2][y+1]]-k)+max(O,sum[1][loc[2][y+1]]-e)]+=dp[k][e][y][step];
}
}
}
}
for(int step=0;step<=n&&step<=900;step++){
ans+=dp[num[0]][num[1]][num[2]][step];
}
cout<<ans<<endl;
return 0;
}