Welcome to Subscribe On Youtube

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 "abcde" 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

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• 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;
      }
  };
  

• 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
  
  

• 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
  }
  

• 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
      }
  }
  
  

All Problems

All Solutions