This problem can be solved with DP (Dynamic Programming).

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

Define \(\mathrm{DP}[i][x]\) as the number of subsequences of the first \(i\) characters of \(S\) that end with \(x\).

We will consider the transitions of “receiving DP.” For example, consider how we can evaluate \(\mathrm{DP}[i][\text{a}]\).

• When \(S_i \neq \text{a}\), we cannot use \(S_i\), so \(\mathrm{DP}[i][\text{a}]=\mathrm{DP}[i-1][\text{a}]\).
• When \(S_i=\text{a}\), there are \(\mathrm{DP}[i-1][\text{a}]\) cases not using \(S_i\). For those using \(S_i\), there are \(\mathrm{DP}[i-1][\text{b}]+\mathrm{DP}[i-1][\text{c}]\) cases of length two or more, because the character right before \(S_i\) cannot be a; and \(1\) case of length \(1\).

In general, we have

\(\mathrm{DP}[i][x]=\begin{cases} \mathrm{DP}[i-1][x] & S_i \neq x \\ \mathrm{DP}[i-1][\text{a}]+\mathrm{DP}[i-1][\text{b}]+\mathrm{DP}[i-1][\text{c}]+1 & S_i = x. \end{cases}\)

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

In this DP, what only differs between \(\mathrm{DP}[i-1]\) and \(\mathrm{DP}[i]\) is \(\mathrm{DP}[i][S_i]\), so we do not have to maintain \(i\) as indices in implementation.

Sample code (C++)

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;

int main(){
  string s;
  cin >> s;
  map<char, mint>dp;
  for(char c: s){
    dp[c] = dp['a'] + dp['b'] + dp['c'] + 1;
  }

  mint ans = 0;
  for(auto[k, v]: dp){
    ans += v;
  }
  cout << ans.val() << endl;
}

Sample code (Python)

from collections import defaultdict
S = input()
dp = defaultdict(int)
for c in S:
  dp[c] = (dp['a'] + dp['b'] + dp['c'] + 1) % 998244353

print(sum(dp.values()) % 998244353)