ある固定した U, T, P, C（この順に並んでいるとします）を集めて UTPC を作る最短手数について考えます。少し考えると、最短手数は

• U と T の間にある文字の有無
• T と P の間にある文字の集合
• P と C の間にある文字の有無

のみに依存することがわかります。

そこで、上記の \(2 \cdot 2^4 \cdot 2 = 64\) 通りすべてについて、最短手数を BFS などで愚直に計算しておきます。（なお、考察が途中でパターン数を減らしきれていないなどで愚直計算に時間がかかる場合でも、結果を埋め込むという手段が考えられます。）

愚直計算の結果を利用すると、あとはいわゆる耳 DP の要領で答えを求めることができます。すなわち、次の状態を持って DP します。

• （今見ている場所）
• 固定する U, T, P, C をどこまで選んだか
• それぞれの間にある文字の有無や集合

DP の状態数や遷移の数は \(5 \cdot 64N\) 等になり、十分間に合います。