With O(N) space, and in len(t)*len(s)

interview-questions
Tags: #<Tag:0x00007f18256d8a78>

#1

Comment body goes here.int Solution::numDistinct(string s, string t) {
map<char,vector > mp;
int n=t.size();
for(int i=n-1;i>=0;i–)
{
mp[t[i]].push_back(i+1);
}
int dp[n+1];
for(int i=0;i<=n;i++)
dp[i]=0;
n=s.size();
for(int i=0;i<n;i++)
{
char ch=s[i];
vector v=mp[ch];
for(int j=0;j<v.size();j++)
{

    if(v[j]==1)
    dp[v[j]]=dp[v[j]]+1;
    else
    dp[v[j]]+=dp[v[j]-1];
   
 }
 
}
return dp[t.size()];

}