\(S\) の長さを \(|S|\) 、 \(S\) の \(i\) 文字目を \(S_i\) と表します。

もし全ての \(i\) で \(S_i\neq S_{i+1}\) なら、全ての部分文字列が条件を満たします。よって求める答えは \(\frac{|S|(|S|+1)}{2}\) です。（先頭と末尾を含む文字と文字の間 \(|S|+1\) 箇所から異なる \(2\) 箇所を選ぶ方法と、選んだ \(2\) 箇所の間の部分文字列が \(1\) 対 \(1\) に対応します）

 S = abac  のとき

  |a|b|a|c|
  ^ ^ ^ ^ ^  ← この 5 箇所から2箇所選ぶ方法と部分文字列が 1 対 1 対応

\(S_i=S_{i+1}\) となる箇所が存在すれば、\(i,i+1\) を同時に選ぶことはできません。よって、\(i\) 文字目までと \(i+1\) 文字目以降に文字列を分割し、 \(2\) つの文字列について答えを求めその和が答えとなります。

 S = abbcabcbaaabc  のとき
    ab|bcabcba|a|abc
    3 +  28 + 1 + 6 = 38

なお、 \(S\) の部分文字列は \(\frac{|S|(|S|+1)}{2}\) 個であることから、答えは \(2^{63}\) 以下であり、64 bit 整数で計算すれば剰余は最後に取るだけで十分です。

以上より \(O(|S|)\) でこの問題を解くことができました。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  string s;
  cin >> s;

  long long ans = 0;
  int start_i = 0;
  for(int i=0; i<s.size(); i++){
    if(i+1 == s.size() || s[i] == s[i+1]){
      ans += (long long) (i - start_i + 1) * (i - start_i + 2) / 2;
      start_i = i + 1;
    }
  }
  cout << ans % 998244353 << endl;
}

実装例 (Python)

S = input()
start_i = 0
ans = 0
for i, c in enumerate(S):
  if i+1 == len(S) or S[i+1] == c:
    ans += (i - start_i + 1) * (i - start_i + 2) // 2
    start_i = i + 1
print(ans % 998244353)