解説で触れられていた「二次元累積和を用いて頑張る」の部分です．各文字を $0, 1, \cdots, 25$ の数字と思います．文字の種類数を $\sigma = 26$ とします．

$dp[val][pos] :=$ 確定した部分の末尾が $val$ かつ最後に $S_i \neq S_{i + 1}$ となった $i$ が $pos$ となる通り数という DP を考えられるのでした．

遷移は $=$ にする場合は DP 配列に対して変更は不要であり，$>$ にする場合は $pos$ に対応した $l$ について $dp[val][pos] \leftarrow dp[val][pos] + (dp[val + 1][l] + \cdots + dp[val + 1][pos - 1]) + \cdots + (dp[\sigma - 1][l] + \cdots + dp[\sigma - 1][pos - 1])$ とすれば良いです．
かっこで囲まれた部分は $dp[val]$ に関する累積和を $\sigma$ 本持ち，更新しつつ DP を進めることで $O(1)$ で入手できます．したがって，更新および累積和の更新は $O(\sigma^2)$ でできます．
ここで，$pos$ を固定したとき，$val = 25, 24, \cdots, 0$ の順に更新することを考えると全体で $O(\sigma)$ でできます．
$<$ にする場合も同様です．

実装例(C++)