“a” から順にアルファベットごとに見ます。 各時点では、同じ文字が隣り合う箇所（残りのアルファベットで埋めないといけない箇所。例えば “aaabaacc” なら \(4\) 箇所）の数だけがポイントになるので、これをキーにして DP にすれば良いです。具体的には、

\({\rm DP}[n][a]\): \(n\) 番目のアルファベットまで見たとき、同じ文字が隣り合う箇所が \(a\) 箇所あるような置き方の数

のような DP で解くことができます。 \({\rm DP}[26][0]\) が求めるものです。 隣り合う箇所 \(a\) を決めると隣り合わない箇所の数も一意に決まるのでこれを \(b\) とします。 \(n\) 番目のアルファベットを見るとき \(f = freq_{n}\) として、これら \(f\) 文字が \(a+b\) 箇所のうち \(i\) 箇所（\(1 \le i \le f\)）に分かれて入り、かつ \(i\) 箇所のうち \(j\) 箇所が \(a\) から選ばれるような選び方は \(_{f-1}C_{i-1} \times _{a}C_{j} \times _{b}C_{i-j}\) で、このとき新しい「同じ文字が隣り合う箇所」の数は \(a + f - i - j\) です。つまり

DP[n][a+f-i-j] += DP[n-1][a] * Comb(f-1, i-1) * Comb(a, j) * Comb(b, i-j)

のような更新をすれば良いです。

AC コード（PyPy 3）