Question

link

Find the number of distinct subsequences of a string (include “” as a subsequence).

For example, Input 

AAA 
ABCDEFG 
CODECRAFT

Output 

4 
128 
496

Solution

In [LeetCode 115] Distinct Subsequences, we discuss finding occurence of a given subsequence.

Now if we do not specify a subsequence, we want the total number of distinct subsequence.

The solution is DP, with the following equation: 

Let, 

dp[i] = number of distinct subsequences ending with a[i]

last[i] = last position of character i in the given string.

Equation: 

dp[i] = dp[last[i] - 1] + ... + dp[i - 1]

The final result is: 

Distinct Subsequences = dp[1] + ... dp[len - 1]

Example 1: 

Input   : - A B C
dp array: 1 1 2 4
Total = 8

Example 2: 

Input   : - A A C
dp array: 1 1 1 3
Total = 6

The code is posted below.

Optimize Solution

There is a good optimization of this DP solution, which is to keep another dp array ‘sum’, which sum[i] = dp[1] + dp[2] + … + dp[i]. The final answer would be sum[len - 1].

This nice idea is from this post. Credit goes to IVlad.

Code

un-optimized code. calculate dp[0] … dp[n], then sum to final result. 

public int countDistinctSubseq(String input) {
    int len = input.length();
    int[] dp = new int[len + 1];
    // dp[i] denotes the number of distinct subseq within first 'i' chars
    dp[0] = 1;
    // the first 0 chars is "" - we consider it as 1 subseq

    for (int i = 1; i <= len; i++) {
        // set dp[i]
        // dp[i] = dp[i-1] + ... + dp[k] where input{k} == input{i}
        int p = i - 1;
        while (p >= 0) {
            dp[i] += dp[p];
            if (p > 0 && input.charAt(p - 1) == input.charAt(i - 1)) {
                // when meeting a same char ahead of position i, stop
                // adding to dp[i]
                break;
            }
            p--;
        }
    }
    int sum = 0;
    for (int i : dp) {
        sum += i;
    }
    return sum;
}