# 16 line C++ solution with O(mn) time and O(m) space

• The basic idea is to go through the S string from start. For any s[i], find if there is a match in T string. If it hits, add DP[j-1] to DP[j],
where DP[j] stands for numbers of subsequences ending with with t[j].
For example,
S:"abcbc"
T:"abc"
When s[i] == 'c', then add up the number of all the distinct subsequences ending with 'b'(that is DP[2] +=DP[1]).
That is when i == 2, there is only one subsequences ending with b, DP[2] = 0+DP[1] = 1.
when i ==4, there are two subsequences ending with b, DP[2] = 1+ DP[1] = 3.

Note that we count j from up to bottom, so when there is duplicates in T, it still works.

class Solution {
public:
int numDistinct(string s, string t) {
vector<int> DP(t.size());
for(int i=0;i<s.size();i++)
for(int j =t.size()-1;j>=0;j--)
if(s[i] == t[j]){
if(j == 0)
DP[0]++;
else
DP[j]+=DP[j-1];
}
return DP[t.size()-1];
}
};

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.