The original version of this problem is based on what was proposed by members of KEYENCE Corp.

First, let us consider the following problem: “given two strings \(S\) and \(T\), what is the minimum number operation of swapping adjacent characters of \(S\) required to make \(S\) equal to \(T\)?” To do so, we can greedily make each character of \(S\) to that of \(T\) one by one.

Now we consider the original problem. Considering determining the characters of resulting string one by one in order, we can come up with the following DP.

\(\text{dp}[i][x][e][y]\) = The number of string \(T\) of length \(i\) that contains \(e\) number of E’s and \(y\) number of Y’s, which requires at least \(x\) operations to make the first \(i\) characters of \(S\) equal to those of \(T\)

We can observe that, after matching the first \(i\) characters of \(S\) to that of \(T\), the remaining part of \(S\) is determined only by \(i\), \(e\), and \(y\). Therefore, once the next character is determined, the number of required operation can be computed in an \(O(|S|)\).

Therefore, the DP works in \(O(|S|^6)\) time. Actually the number of states is about \(\frac{1}{54}|S|^5\), even if the implementation has not really good constant factor, it will be fast enough to finish within the time limit.

Sample code(Python) (uses associative arrays for DP, 331ms)

With a proper precomputation, the DP transition can be done in an \(O(1)\) time, so the overall complexity can be reduced to \(O(|S|^5)\).