先考虑对于固定的字符串 \(S,T\)，将 \(S\) 变成 \(T\) 的最小操作次数是什么。
显然 \(S\) 中 \(K,E,Y\) 内部的相对顺序都不会变，即 \(T\) 中第一个 \(K\) 是 \(S\) 中第一个 \(K\) 交换过来的，\(T\) 中第三个 \(E\) 是 \(S\) 中第三个 \(E\) 交换过来的，诸如此类。也由此得出最坏情况下交换次数也至多是 \(\frac{n\times(n-1)}{2}\) 左右。
下文称一个串的距离为原串变成它的最小操作次数。
以此可以得到设 \(f_{i,j,k,l}\) 表示已经填了 \(i\) 个 \(K\)，\(j\) 个 \(E\)，\(k\) 个 \(Y\)，距离为 \(l\) 的方案数，转移就枚举下一个填什么。
时间复杂度 \(\mathcal O(\left|S\right|^6)\)，但是常数特别特别小（只跑了 \(16\text{ms}\)），也可以通过预处理将复杂度降为 \(\mathcal O(\left|S\right|^5)\)。
Code：
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
const int N = 35;
int n, K;
ll f[N][N][N][505];
char s[N];
vector <int> v[3];
int main() {
scanf("%s%d", s + 1, &K);
n = strlen(s + 1);
for (int i = 1; i <= n; ++i) {
if (s[i] == 'K') v[0].pb(i);
if (s[i] == 'E') v[1].pb(i);
if (s[i] == 'Y') v[2].pb(i);
}
f[0][0][0][0] = 1;
int a = v[0].size(), b = v[1].size(), c = v[2].size();
for (int i = 0; i <= a; ++i)
for (int j = 0; j <= b; ++j)
for (int k = 0; k <= c; ++k)
for (int l = 0; l <= min(K, n * (n - 1) / 2); ++l) {
if (!f[i][j][k][l]) continue;
if (i < a) {
int p = v[0][i], cnt = l;
for (int t = 0; t < j; ++t) cnt += v[1][t] > p;
for (int t = 0; t < k; ++t) cnt += v[2][t] > p;
f[i + 1][j][k][cnt] += f[i][j][k][l];
}
if (j < b) {
int p = v[1][j], cnt = l;
for (int t = 0; t < i; ++t) cnt += v[0][t] > p;
for (int t = 0; t < k; ++t) cnt += v[2][t] > p;
f[i][j + 1][k][cnt] += f[i][j][k][l];
}
if (k < c) {
int p = v[2][k], cnt = l;
for (int t = 0; t < i; ++t) cnt += v[0][t] > p;
for (int t = 0; t < j; ++t) cnt += v[1][t] > p;
f[i][j][k + 1][cnt] += f[i][j][k][l];
}
}
ll ans = 0;
for (int i = 0; i <= min(K, n * (n - 1) / 2); ++i) ans += f[a][b][c][i];
printf("%lld", ans);
return 0;
}