[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].

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.

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