[LeetCode] Distinct Subsequences (Java)

Given a string S and a string T, count the number of distinct subsequences of T in S.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Here is an example:
S = "rabbbit"T = "rabbit"

Return 3.

Analysis

This is a DP problem. We can use num[i][j] to save the number of distinct subsequences of T(0, j) in S(0, i). We know that for any number i, num[i][0] = 1 because we need to delete all characters from S(0, i) to a empty string.

If the character at position i in S is equal to the character at position j in T, there are two options.

  1. Delete the character at position i in S. Then the number of distinct subsequences should be the number of distinct subsequences of T(0, j) in S(0, i – 1).
  2. Remains the character at position i in S. Then the number is the number of distinct subsequences of T(0, j – 1) in S(0, i – 1).

So num[i][j] = num[i – 1][j] + num[i – 1][j – 1].

If the character at position i in S is not equal to the character at position j in T, then we can only delete this character. So num[i][j] = num[i – 1][j].

Code

Complexity

The complexity is $O(mn)$.

 

  • Charlie

    Could you tell me what plugin you are using for code formatting? The page layout looks awesome!

    • decoet

      I use Crayon Syntax Highlighter to highlight the code. But I think this plugin is quite big for user to load it when they use a slow internet connection.

  • rahul

    can you help me to understand problem.
    S = “rabbbit”, T = “rabbit”
    T has many distinct subsequence Eg. rabbit, rab, rait , rabit, ait, bit, ans many more
    ans all of them present in S.
    Then how the answer is 3.
    Thanks in advance

    • decoet

      T is a fixed string “rabbit”. If we make S in this way: “r a b1 b2 b3 i t”, we can have 3 different subsequences that are actually “rabbit”: “r a b1 b2 i t”, “r a b1 b3 i t”, “r a b2 b3 i t”.

      So the answer here is 3.

  • I have a solution using less space:

    public class Solution {
    public int numDistinct(String s, String t) {
    if(s == null || t == null || t.length() == 0) return 0;
    int[] dp = new int[t.length()];

    for(int i = 0; i=0; j–){
    if(c == t.charAt(j)){
    dp[j] = dp[j] + (j!=0?dp[j-1]: 1);
    }
    }
    }
    return dp[t.length()-1];
    }
    }

    URL: http://traceformula.blogspot.com/2015/08/distinct-subsequences.html

  • I have a solution using less space:

    public class Solution {
    public int numDistinct(String s, String t) {
    if(s == null || t == null || t.length() == 0) return 0;
    int[] dp = new int[t.length()];

    for(int i = 0; i<s.length(); i++){
    char c = s.charAt(i);
    for(int j=dp.length-1; j>=0; j–){
    if(c == t.charAt(j)){
    dp[j] = dp[j] + (j!=0?dp[j-1]: 1);
    }
    }
    }
    return dp[t.length()-1];
    }
    }
    URL: http://traceformula.blogspot.com/2015/08/distinct-subsequences.html

    • decoet

      Cool!

      Yes. Since we only care about the state in last iteration, we can use one dimension DP to do this.