この問題は DP により解くことができます。

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

\(\mathrm{DP}[i][x]\) を「\(S\) の \(i\) 文字目までからなる部分列のうち、末尾が \(x\) であるものの個数」とします。

もらう DP の遷移を考えます。例として \(\mathrm{DP}[i][\text{a}]\) を求めることを考えます。

• \(S_i \neq \text{a}\) のとき、\(S_i\) を使うことはできません。よって \(\mathrm{DP}[i][\text{a}]=\mathrm{DP}[i-1][\text{a}]\) です。
• \(S_i=\text{a}\) のとき、\(S_i\) を使わないケースが \(\mathrm{DP}[i-1][\text{a}]\) 通り、 \(S_i\) を使う長さ \(2\) 以上の部分列では \(S_i\) の前が a であってはならないので \(\mathrm{DP}[i-1][\text{b}]+\mathrm{DP}[i-1][\text{c}]\) 通り、\(S_i\) を使う長さ \(1\) の部分列が \(1\) 通りとなります。

一般に

\(\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}\)

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

この DP では、 \(\mathrm{DP}[i-1]\) と \(\mathrm{DP}[i]\) で違いがあるのは \(\mathrm{DP}[i][S_i]\) のみです。よって \(i\) を添え字に持つことなく実装することができます。

実装例 (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;
}

実装例 (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)