计算不同子序列的数量

给定一个字符串 str，我们需要找出可以由它组成的 不同子序列（distinct subsequences） 的数量。

子序列是指通过从原始字符串中删除零个或多个字符而不改变剩余字符的相对顺序而导出的序列。

注意： 答案可能非常大，因此输出将是答案对 10^9+7 取模的结果。
示例：

> 输入： str = "gfg"

> 输出： 7

> 解释： 这七种不同的子序列是 ""、"g"、"f"、"gf"、"fg"、"gg" 和 "gfg"。

>

> 输入： str = "ggg"

> 输出： 4

> 解释： 这四种不同的子序列是 ""、"g"、"gg" 和 "ggg"。

目录

• [朴素方法] 通过生成所有子序列 – O(2^n) 时间和 O(2^n) 空间
• [预期方法] 使用动态规划 – O(n) 时间和 O(n) 空间
• [空间优化] – O(n) 时间和 O(1) 空间

[朴素方法] 通过生成所有子序列 – O(2^n) 时间和 O(2^n) 空间

> 这个思路是生成字符串每一个可能的子序列，并将它们存储在 HashSet 中以确保唯一性。为此，我们对字符串的每个索引应用递归。对于索引 i 处的每个字符，我们有两种选择：

>

> – 包含 str[i]：将当前字符添加到正在构建的子序列中，并移动到下一个索引。

> – 排除 str[i]：跳过当前字符，并移动到下一个索引。

>

> 当我们到达字符串末尾时递归停止，这意味着没有更多的字符需要处理。此时，我们将生成的子序列插入到 HashSet 中。

C++

//Driver Code Starts
#include 
#include 
#include 
using namespace std;

//Driver Code Ends

const int mod = 1e9+7;

void generateSubseq(int ind, string &cur, string &str, unordered_set &s) {
    int n = str.size();

    // if the end of string is reached
    // store the subsequence in set
    if(ind == n) {
        s.insert(cur); 
        return;
    }

    // skip the current character
    generateSubseq(ind + 1, cur, str, s);

    // add the character str[i]
    cur.push_back(str[ind]);
    generateSubseq(ind + 1, cur, str, s);

    // remove the added character
    cur.pop_back();
}

int distinctSubseq(string &str) {
    
    // to store the unique subsequences
    unordered_set s;

    // to store current subsequence
    string cur;

    generateSubseq(0, cur, str, s);

    int ans = (int)s.size();
    return ans % mod;
}

//Driver Code Starts

int main() {
    string str = "gfg";
    cout << distinctSubseq(str);
    return 0;
}

//Driver Code Ends

CODEBLOCK_e84800e5


Python

mod = 1000000007

def generateSubseq(ind, cur, s, st):
    n = len(s)

    # if the end of string is reached
    # store the subsequence in set
    if ind == n:
        st.add(cur)
        return

    # skip the current character
    generateSubseq(ind + 1, cur, s, st)

    # add the character s[i]
    generateSubseq(ind + 1, cur + s[ind], s, st)

def distinctSubseq(s):

    # to store the unique subsequences
    st = set()

    # to store current subsequence
    cur = ""

    generateSubseq(0, cur, s, st)

    ans = len(st)
    return ans % mod

#Driver Code Starts

if __name__ == "__main__":
    s = "gfg"
    print(distinctSubseq(s))

#Driver Code Ends

“

//Driver Code Starts

using System;

using System.Text;

using System.Collections.Generic;

class GFG {

//Driver Code Ends

static int mod = 1000000007;

sta