より高速な解法の概略を記します。

包除原理で解きます。

各文字種について、同じ文字が必ず隣接する個数を決め打つと、何個かの連結した成分に分けられます。分け方は、二項係数で求まります。後は、分けた成分をどのように並べるかを上手く求めたいです。

これは、指数型母関数の形で持ち、積を取ればよいです。任意 mod 畳み込みを用いると、freq の最大値を \(N\) として、\(\mathrm{O}(\sigma N \log^2(\sigma N))\) (\(\sigma\) は wordsize(26)) でこの問題を解くことが出来ました。