题目描述

给定一个字符串 S，计算 S 的不同非空子序列的个数。

因为结果可能很大，所以返回答案模 10^9 + 7.

样例

示例 1：

输入："abc"
输出：7
解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。
示例 2：

输入："aba"
输出：6
解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。
示例 3：

输入："aaa"
输出：3
解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

算法1

(dp) $O(n^2)$

要求不重复子字符串,就从长度为1开始,从短到长开始算
sum[ i ] 表示前i个字符串组成的长度为j的不重复子字符串的个数( j最开始是1,因为是从2 ~ n顺序枚举，所以省去j变量 )
然后从尾部往前面开始计算,遇到重复的跳过.
举例来说：
当为S[ i ]时,如果S[ j ]等于S[ i ]并且j>i就跳过.因为重复了
否则就是总数就加上sum[ i - 1 ].

cnt[i]表示以i结尾的长度为j+1的不同字符串的个数
最后要更新sum[ i ],令其表示为表示前i个字符串组成的长度为j+1的不重复子字符串的个数.
那么就要对cnt[i]进行累加,并且去掉重复的字符串的个数,具体来说,就是减去前一个末尾字符串相同的数量

时间复杂度分析：双重循环$O(n^2)$

C++ 代码

class Solution {
public:
int distinctSubseqII(string S) {
    int n = S.length();
    long mod = 1e9 + 7;
    long tot =  0;
    vector< long > sum( n + 1, 0 ), cnt( n + 1, 0 );
    vector< int > Index( 26, 0 );
    for( int i = 0; i < n; ++ i )
    {
        sum[ i + 1 ] = sum[ i ];
        if( Index[ S[ i ] - 'a' ] != 1 ) sum[ i + 1 ] ++;
        Index[ S[ i ] - 'a' ] = 1;
    }
    tot = sum[ n ];
    for( int i = 2; i <= n; ++ i )
    {
        for( int j = n - 1; j >= i - 1; -- j )
        {
            if( Index[ S[ j ] - 'a' ] != i )  tot = ( tot + sum[ j ]  ) % mod;
            Index[ S[ j ] - 'a' ] = i;
            cnt[ j + 1 ] = sum[ j ];
        }
        for( int j = i - 1; j >= 1; j -- ) cnt[ j ] = 0;
        vector< int > Index1( 26, -1 );
        for( int i = 1; i <= n; i ++ )
        {
            int tmp = cnt[ i ];
            sum[ i ] = ( sum[ i - 1 ] + tmp ) % mod;
            if( Index1[ S[ i - 1 ] - 'a' ] != -1 ) sum[ i ] = ( sum[ i ] - Index1[ S[ i - 1 ] - 'a' ] + mod ) % mod;
            Index1[ S[ i - 1 ] - 'a' ] = tmp;
        }
    }
    return tot;
}
};

算法2

(dp) $O(n)$

从空字符串开始算
以aba举例来说
dp[ 0 ] = 1 空字符串 记为 *
dp[ 1 ] = 2 * a
dp[ 2 ] = 4 * a b ab 在1的基础上再加上b
dp[ 3 ] = 8 - dp[ 0 ] * a b ab a aa ba aba 本来应该是8, 但是a重复了, 需要减去重复的，记录上次a出现的位置为1, 那应该减去上次a出现的位置的前一个位置,也就是0

时间复杂度分析：一重循环 $O(n)$

C++ 代码

class Solution {
public:
    int distinctSubseqII(string S) {
        auto n = S.length();
        long mod = 1e9 + 7;
        vector< long > dp( n + 1, 0 );
        vector< int > pre( 26, -1 );
        dp[ 0 ] = 1;
        for( int i = 1; i <= n; ++ i )
        {
            dp[ i ] = dp[ i - 1 ] * 2 % mod;
            if( pre[ S[ i - 1 ] - 'a' ] != -1 ) dp[ i ] = ( dp[ i ] - dp[ pre[ S[ i - 1 ] - 'a' ] - 1 ] + mod ) % mod;
            pre[ S[ i - 1 ] - 'a' ] = i;
        }
        return dp[ n ] - 1;
    }
};