# 115. Distinct Subsequences

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

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

Example 1:

Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:

As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^

Example 2:

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:

As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

# Solution

Approach 1: DP.

# Code (Python)

Approach 1:

    def numDistinct(self, s: str, t: str) -> int:
        # match[i][j]: ways for the first i chars in s to match the first j chars in t
        match = [[0 for _ in range(len(t) + 1)] for _ in range(len(s) + 1)]
        for i in range(len(match)):
            match[i][0] = 1 # 1 way for anything to match an empty string
        
        for i in range(1, len(match)):
            for j in range(1, len(match[0])):
                if s[i-1] != t[j-1]:
                    match[i][j] = match[i-1][j] # use the previous portion of s to match t
                else:
                    match[i][j] = match[i-1][j] + match[i-1][j-1] # in addition, match the last char of s to the last char of t
        
        return match[-1][-1]

# Code (C++)

Approach 1:

// DP - 2D.
class Solution {
public:
    int numDistinct(string s, string t) {
        int nS = s.size();
        int nT = t.size();
        if (nS < nT)
            return 0;
        long res[nT+1][nS+1];
        res[0][0] = 1;
        for (int i = 1; i <= nT; ++i)
            res[i][0] = 0;
        for (int i = 1; i <= nS; ++i)
            res[0][i] = 1;
        for (int i = 1; i <= nT; ++i)
        {
            for (int j = i; j <= nS; ++j)
            {
                res[i][j] = 0;
                if (j > i)
                    res[i][j] += res[i][j-1];
                if (t[i-1] == s[j-1])
                    res[i][j] += res[i-1][j-1];
            }
        }
        return res[nT][nS];
    }
};

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