In this post, we are going to solve the 940. Distinct Subsequences II problem of Leetcode. This problem 940. Distinct Subsequences II is a Leetcode hard level problem. Let’s see the code, 940. Distinct Subsequences II – Leetcode Solution.

Problem

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.

Now, let’s see the code of 940. Distinct Subsequences II – Leetcode Solution.

Distinct Subsequences II – Leetcode Solution

940. Distinct Subsequences II – Solution in Java

class Solution {
    public int distinctSubseqII(String s) {
        int[] dp = new int[s.length()+1];
        int mod = 1000000007;
        HashMap<Character,Integer> map = new HashMap<>();
        
        dp[0] = 1;
        for(int i=1; i<= s.length();i++){
            dp[i] = (dp[i-1]%mod * 2)%mod;
            if(map.containsKey(s.charAt(i-1))){
                int lo = map.get(s.charAt(i-1));
                dp[i] = (dp[i]-dp[lo-1]+mod)%mod;
            }
            map.put(s.charAt(i-1),i);
        }
        return dp[s.length()] - 1;
    }
}

940. Distinct Subsequences II – Solution in C++

class Solution {
public:
    const int mod = 1e9 + 7 ;
    int distinctSubseqII(string s) {
        
        long long n = s.size();
        
        vector<long long> dp ( n + 1 , 0 );
        dp[0] = 1;
        
        map<char , long long> m;
        for(long long i = 1; i < n + 1 ;i++){
            
            dp[i] =( 2 * dp[i - 1] + mod) % mod;
            
            if ( m.count(s[i - 1]) ){
                
                long long index = m[s[i - 1]];
                dp[ i ] = (dp[i] - dp[ index - 1] + mod) % mod;
                
            }
            
            m[s[i - 1]] = i;
        }
        
        return dp[n] - 1;
    }
};

940. Distinct Subsequences II – Solution in Python

class Solution(object):
    def distinctSubseqII(self, S):
        """
        :type S: str
        :rtype: int
        """
        m = 10**9 + 7
        l = len(S)
        hash_map = {}
        dp = [0] * (l+1)
        dp[0] = 1
        for i in range(l):
            dp[i+1] = 2*dp[i]
            if S[i] in hash_map:
                dp[i+1] = dp[i+1] - dp[hash_map[S[i]] - 1]
            hash_map[S[i]] = i+1
        
        return (dp[-1] - 1)%m

Note: This problem 940. Distinct Subsequences II is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.