Let \(|S|\) denote the length of \(S\), and \(S_i\) the \(i\)-th character of \(S\).

If \(S_i\neq S_{i+1}\) for all \(i\), then all strings satisfy the conditon, so the sought count is \(\frac{|S|(|S|+1)}{2}\). (There is a one-to-one correspondence between a way to choose two partitions among the \((|S| + 1)\) partitions including the beginning and the end, and the substring between the two partitions.)

 If S = abac

  |a|b|a|c|
  ^ ^ ^ ^ ^  ← Choosing two out of these five corresponds one-to-one to a substring

If there is a position where \(S_i=S_{i+1}\), we cannot choose \(i\) and \((i+1)\) simultaneously. Therefore, the answer is obtained by splitting the string between the \(i\)-th and \((i+1)\)-th string, evaluating the count for each block, and finding the sum.

 If S = abbcabcbaaabc
    ab|bcabcba|a|abc
    3 +  28 + 1 + 6 = 38

Since there are \(\frac{|S|(|S|+1)}{2}\) substrings of \(S\), the answer is at most \(\frac{|S|(|S|+1)}{2}\), which fits in a 64-bit integer type; it is sufficient to take modulus only once at the end.

Hence, the problem has been solved in a total of \(O(|S|)\) time.

Sample code (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;
}

Sample code (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)