The number of distinct strings that can be obtained as a permutation of non-empty contiguous subsequence \(S'\) of \(S\) depends only on the number of appearance of each alphabet in \(S'\).

Therefore, in order to boil this problem down to DP (Dynamic Programming), it is important to hold the following two states:

• how many alphabets have been consumed?
• how many characters has been used so far?

Therefore, the following DP is valid.

• \(\text{dp}_{i,j}:=(\)the number of subsequences of \(S\) consisting of the first \(i\) alphabets and of length \(j\), and their permutations\()\)

The transition can be written as follows, where the number of appearances of a through z in \(S\) is denoted by \(\text{freq}_1,\text{freq}_2,\ldots,\text{freq}_{26}\).

• \(\text{dp}_{i,j} = \sum_{k=0}^{\min(j,\text{freq}_i)} \text{dp}_{i-1,j-k} \times \binom{j}{k}\)

At a glance, the complexity seems to be \(O(σN^2)\) where \(σ=26\) and \(N\) is the length of \(S\); however, since the transition to \(\text{dp}_{i,j}\) requires at most \(O(\text{freq}_i)\) time, the total complexity is at most \(O(\sum_{i=1}^{26} \text{freq}_i \times N)=O((\sum_{i=1}^{26} \text{freq}_i) \times N)=O(N \times N)=O(N^2)\).

The desired answer is \(\sum_{i=1}^{N} \text{dp}_{26,i}\).

Sample code (C++)

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

using ll = long long;

const ll MAX = 5010, MOD = 998244353;

vector<ll> fac,finv,inv;

void binom_init() {
    fac.resize(MAX);
    finv.resize(MAX);
    inv.resize(MAX);
    fac[0] = fac[1] = 1;
    inv[1] = 1;
    finv[0] = finv[1] = 1;
    for(int i=2; i<MAX; i++){
        fac[i] = fac[i-1]*i%MOD;
        inv[i] = MOD-MOD/i*inv[MOD%i]%MOD;
        finv[i] = finv[i-1]*inv[i]%MOD;
    }
}

ll binom(ll n, ll r){
    if(n<r || n<0 || r<0) return 0;
    return fac[n]*finv[r]%MOD*finv[n-r]%MOD;
}

int main(){
    binom_init();
    string S; cin >> S;
    int N = S.size();
    vector<int> freq(26);
    for(auto el: S) freq[el-'a']++;
    vector<vector<ll>> dp(27,vector<ll>(N+1));
    dp[0][0] = 1;
    for(int i=0; i<26; i++){
        for(int j=0; j<=N; j++){
            for(int k=0; k<=min(j,freq[i]); k++){
                dp[i+1][j] += dp[i][j-k]*binom(j,k);
                dp[i+1][j] %= MOD;
            }
        }
    }
    ll ans = 0;
    for(int i=1; i<=N; i++){
        ans += dp[26][i];
        ans %= MOD;
    }
    cout << ans << endl;
}