$N= |S|$ として $O(N \log N)$ で解く方法を紹介します。
初めに、 $S$ がどの文字を何個含んでいるかのみが重要なので、各文字の出現回数を数えます。 $\sigma _{c}$ を文字 $c$ の個数とします。

a から順に部分文字列が含む文字の個数を決めていくとします。ここで、ある文字を $i$ 個選んだとします。この時、「部分文字列を並び替えてできる文字列の数」を「同じ文字を区別した場合に部分文字列を並び替えてできる文字列の数」で割った値は $\frac{1}{i!}$ 倍されます。( $6$ 人のグループを $1,2,3$ 人のグループに分ける際の式である $\frac{6!}{1!2!3!}$ における分母のようなイメージです。)

よって、以下の多項式を掛け合わせたものの式の $i > 0$ について、 $x^i$ の係数に $i!$ をかけたものの総和が答えとなります。ここで、 $0!=1$ とします。
$\left( \frac{1}{0!} x^0 + \frac{1}{1!} x^1 + \cdots + \frac{1}{\sigma _{c}!} x^{\sigma _{c}} \right)$ $($ $c=$ a,b, $\cdots$ ,z $)$

計算量は $O(N \log N)$ です。実装の際はACLのconvolutionを使うと楽です。

実装例