Let’s consider the minimum number of operations needed to transform the string \(S\) into another string \(T\) with the same number of As, Bs, and Cs as \(S\).

Let \(C[x][y]\) denote the number of positions where \(S\) has the character \(x\) and \(T\) has the character \(y\).

The minimum number of operations is determined solely by \(C[x][y]\). Specifically, it can be calculated as follows:

• First, if \(C[x][y] > 0\) and \(C[y][x] > 0\) for \(x \neq y\), then one operation to swap characters \(x\) and \(y\) can reduce the values of \(C[x][y]\) and \(C[y][x]\) by \(1\) each. It is beneficial to perform as many such operations as possible.

• When the above operation can no longer be performed, we have \(C[\)A\(][\)B\(] = C[\)B\(][\)C\(] = C[\)C\(][\)A\(]\), and let \(X\) denote this value. Also, we have \(C[\)A\(][\)C\(] = C[\)C\(][\)B\(] = C[\)B\(][\)A\(]\), and let \(Y\) denote this value. At least one of \(X\) and \(Y\) is \(0\). If \(X > 0\), then we can reduce \(X\) by \(1\) with two operations: ABC \(\to\) BAC \(\to\) BCA. It is optimal to perform as many such operations as possible. The same applies to \(Y\), where it is optimal to reduce it by \(1\) with two operations.

We need to count the number of strings \(T\) that can be made with \(K\) or fewer operations in this way. Once we fix all \(C[x][y]\), the number of corresponding strings \(T\) can be found with binomial coefficients.

Fixing \(C[x][y]\) is equivalent to fixing the number of operations in the optimal procedure described above.

There are four degrees of freedom: the number of operations for \((x, y) = (\)A,B\(), (\)A,C\(), (\)B,C\()\) in the first type of operation, and the value of \(X\) (or \(Y\)) in the second type of operation. We will try all possible combinations of these.

As a result, the number of procedures to consider is \(O(K^4)\), which is computationally feasible.

Therefore, this problem can be solved in \(O(N + K^4)\) time in total.

Sample Solution