Question

940. Distinct Subsequences II

中文文档

Description

Given a string s, return _the number of distinct non-empty subsequences of_ s. Since the answer may be very large, return it modulo 109 + 7.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of &quot;<u>a</u>b<u>c</u>d<u>e</u>&quot; while "aec" is not.

 

Example 1:

Input: s = "abc"
Output: 7
Explanation: The 7 distinct subsequences are "a", "b", "c", "ab", "ac", "bc", and "abc".

Example 2:

Input: s = "aba"
Output: 6
Explanation: The 6 distinct subsequences are "a", "b", "ab", "aa", "ba", and "aba".

Example 3:

Input: s = "aaa"
Output: 3
Explanation: The 3 distinct subsequences are "a", "aa" and "aaa".

 

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase English letters.

Solutions

Solution 1

class Solution:
  def distinctSubseqII(self, s: str) -> int:
    mod = 10**9 + 7
    n = len(s)
    dp = [[0] * 26 for _ in range(n + 1)]
    for i, c in enumerate(s, 1):
      k = ord(c) - ord('a')
      for j in range(26):
        if j == k:
          dp[i][j] = sum(dp[i - 1]) % mod + 1
        else:
          dp[i][j] = dp[i - 1][j]
    return sum(dp[-1]) % mod

class Solution {
  private static final int MOD = (int) 1e9 + 7;

  public int distinctSubseqII(String s) {
    int[] dp = new int[26];
    for (int i = 0; i < s.length(); ++i) {
      int j = s.charAt(i) - 'a';
      dp[j] = sum(dp) + 1;
    }
    return sum(dp);
  }

  private int sum(int[] arr) {
    int x = 0;
    for (int v : arr) {
      x = (x + v) % MOD;
    }
    return x;
  }
}

class Solution {
public:
  const int mod = 1e9 + 7;

  int distinctSubseqII(string s) {
    vector<long> dp(26);
    for (char& c : s) {
      int i = c - 'a';
      dp[i] = accumulate(dp.begin(), dp.end(), 1l) % mod;
    }
    return accumulate(dp.begin(), dp.end(), 0l) % mod;
  }
};

func distinctSubseqII(s string) int {
  const mod int = 1e9 + 7
  sum := func(arr []int) int {
    x := 0
    for _, v := range arr {
      x = (x + v) % mod
    }
    return x
  }

  dp := make([]int, 26)
  for _, c := range s {
    c -= 'a'
    dp[c] = sum(dp) + 1
  }
  return sum(dp)
}

function distinctSubseqII(s: string): number {
  const mod = 1e9 + 7;
  const dp = new Array(26).fill(0);
  for (const c of s) {
    dp[c.charCodeAt(0) - 'a'.charCodeAt(0)] = dp.reduce((r, v) => (r + v) % mod, 0) + 1;
  }
  return dp.reduce((r, v) => (r + v) % mod, 0);
}

impl Solution {
  pub fn distinct_subseq_ii(s: String) -> i32 {
    const MOD: i32 = (1e9 as i32) + 7;
    let mut dp = [0; 26];
    for u in s.as_bytes() {
      let i = (u - &b'a') as usize;
      dp[i] =
        ({
          let mut sum = 0;
          dp.iter().for_each(|&v| {
            sum = (sum + v) % MOD;
          });
          sum
        }) + 1;
    }
    let mut res = 0;
    dp.iter().for_each(|&v| {
      res = (res + v) % MOD;
    });
    res
  }
}

int distinctSubseqII(char* s) {
  int mod = 1e9 + 7;
  int n = strlen(s);
  int dp[26] = {0};
  for (int i = 0; i < n; i++) {
    int sum = 0;
    for (int j = 0; j < 26; j++) {
      sum = (sum + dp[j]) % mod;
    }
    dp[s[i] - 'a'] = sum + 1;
  }
  int res = 0;
  for (int i = 0; i < 26; i++) {
    res = (res + dp[i]) % mod;
  }
  return res;
}

Solution 2

class Solution:
  def distinctSubseqII(self, s: str) -> int:
    mod = 10**9 + 7
    dp = [0] * 26
    for c in s:
      i = ord(c) - ord('a')
      dp[i] = sum(dp) % mod + 1
    return sum(dp) % mod

class Solution {
  private static final int MOD = (int) 1e9 + 7;

  public int distinctSubseqII(String s) {
    int[] dp = new int[26];
    int ans = 0;
    for (int i = 0; i < s.length(); ++i) {
      int j = s.charAt(i) - 'a';
      int add = (ans - dp[j] + 1) % MOD;
      ans = (ans + add) % MOD;
      dp[j] = (dp[j] + add) % MOD;
    }
    return (ans + MOD) % MOD;
  }
}

class Solution {
public:
  const int mod = 1e9 + 7;

  int distinctSubseqII(string s) {
    vector<long> dp(26);
    long ans = 0;
    for (char& c : s) {
      int i = c - 'a';
      long add = ans - dp[i] + 1;
      ans = (ans + add + mod) % mod;
      dp[i] = (dp[i] + add) % mod;
    }
    return ans;
  }
};

func distinctSubseqII(s string) int {
  const mod int = 1e9 + 7
  dp := make([]int, 26)
  ans := 0
  for _, c := range s {
    c -= 'a'
    add := ans - dp[c] + 1
    ans = (ans + add) % mod
    dp[c] = (dp[c] + add) % mod
  }
  return (ans + mod) % mod
}

Solution 3

class Solution:
  def distinctSubseqII(self, s: str) -> int:
    mod = 10**9 + 7
    dp = [0] * 26
    ans = 0
    for c in s:
      i = ord(c) - ord('a')
      add = ans - dp[i] + 1
      ans = (ans + add) % mod
      dp[i] += add
    return ans