公式解説における \(T = \) 文字の集合 に加え、\(k = \) 最後の文字の位置 - 最初の文字の位置 を添え字に持ってbit-dpをします。

このとき、Cyanmondさんの解説 https://atcoder.jp/contests/joig2023-open/editorial/5624 のような実装をしなくても、\(k\) について、まだ出てきていない {最後の文字, 最初の文字} の寄与を \(0\) として扱い、出てきたら足し引きすることで、\(O(N+2^K K^2+QK)\) 解法が簡潔に実装できます。

実装例：https://atcoder.jp/contests/joig2023-open/submissions/65214364 （公式解説とは異なり、右に動く回数の最小化を行っています）