不同的子序列 II

Leetcode题目链接

描述

详见中文题目链接。

解答

class Solution {
public:
    int distinctSubseqII(string s) {
        const int MOD = 1e9 + 7;
        array<int, 26> count{};
        int all = 1, newAdd;

        for (const char& ch : s) {
            newAdd = (all - count[ch - 'a'] + MOD) % MOD;
            count[ch - 'a'] = (count[ch - 'a'] + newAdd) % MOD;
            all = (all + newAdd) % MOD;
        }
        return (all - 1 + MOD) % MOD;
    }
};