\(S\) の \(i\) 文字目から \(j\) 文字目までを取り出した連続部分文字列を \(S_{i,j}\) と表記します。

\(S_{i,j}\) のなかで同じ文字が連続している箇所があるような \((i,j)\) の組を数える問題です。

ここで、\((S_{i,j}\) のなかで同じ文字が連続している箇所があるような \((i,j)\) の組数\() = ((i,j)\) の組数\() - (S_{i,j}\) のなかで同じ文字が連続している箇所が存在しないような \((i,j)\) の組数\()\) が成り立ちます。

\(S\) を、同じ文字が連続している箇所で分けます。
例えば mississippi であれば、mis, sis, sip, pi と分けます。
「分けた各文字列に対する連続部分文字列の個数」の和がそのまま \((S_{i,j}\) のなかで同じ文字が連続している箇所が存在しないような \((i,j)\) の組数\()\) となります。

特に長さ \(n\) の文字列に対する連続部分文字列の個数は \(\displaystyle \frac{n(n+1)}{2}\) です。