文字種数を \(K\) とします。

公式解説では \(S[1]\) と \(S[N]\) の文字を固定して \(O(N + 2^K K^3 + QK)\) の計算量を実現していますが、イメージはしづらいですが固定しなくても解けます。

bitDP における集合を表すキーを \(s\) とします。

• \(s\) に \(S[1]\) も \(S[N]\) も含まれていない場合
  • そのままでよいです。
• \(s\) に \(S[1]\) と \(S[N]\) のどちらかが含まれている場合
  • 含まれている方の位置 (と、どちらが含まれているか) の情報のキーを追加します。
• \(s\) に \(S[1]\) と \(S[N]\) のどちらも含まれている場合
  • \(S[N]\) の位置と \(S[1]\) の位置の差分の情報のキーを追加します。

以上のようにキーを付け足した DP により、考えられる \(S[1]\) と \(S[N]\) の位置の差分それぞれに対して最適解が求まります。
この DP は前計算を含めて時間計算量 \(O(2^K K^2)\) で動作します。よって、全体の時間計算量は \(O(N + 2^K K^2 + QK)\) となります。