この問題の原案はキーエンス社の社員により提供されたものをもとに作られました

まずは「\(2\) つの文字列 \(S\) と \(T\) が与えられたとき、\(S\) の隣接 \(2\) 文字を入れ替える操作を最小で何回行えば \(T\) と一致させることができるか？」という問題を考えます。これは\(S\) の先頭から順に貪欲に \(T\) に一致させるようにすればよいです。

もとの問題を考えます。先頭から順に文字列を作り変えるように考えることで次のようなDPができます。

\(\text{dp}[i][x][e][y]\) = 長さ \(i\) の文字列 \(T\) であって、E を \(e\) 個、Y を \(y\) 個含み、\(S\) の \(i\) 文字目までを \(T\) と一致させるために \(x\) 回の操作が必要なものの個数

少し考えると、\(S\) の \(i\) 文字目までを \(T\) と一致させるために操作を行った後の、\(S\) の \(i\) 文字目より後の状態は \(i,e,y\) のみによって決まることがわかります。したがって、次の \(1\) 文字を決めるときの操作回数は \(O(|S|)\)で求めることができます。

以上により、このDPは \(O(|S|^6)\) で動作します。実際には状態数が \(\frac{1}{54}|S|^5\) 程度であることから、多少定数倍の悪い実装をしても実行時間には十分間に合います。

実装例(Python) (DPに連想配列を使用, 331ms)

適切な前計算の下でDPの遷移を \(O(1)\) で行えるため、全体で \(O(|S|^5)\) で求めることもできます。