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

Have you met this question in a real interview? Yes
Example
Given S = "rabbbit", T = "rabbit", return 3.

Challenge 
Do it in O(n2) time and O(n) memory.

O(n2) memory is also acceptable if you do not know how to optimize memory.

public int numDistinct(String S, String T) {
        // write your code here
        //state 
        int m = S.length();
        int n = T.length();
        
        // initialize
        int[][] f = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i++) {
            f[i][0]= 1;
        }
        for (int j = 1; j <= n; j++) {
            f[0][j] = 0;
        }
        
        //function
        for (int i = 1; i<= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    f[i][j] = f[i- 1][j - 1] + f[i - 1][j];
                } else {
                    f[i][j] = f[i - 1][j];
                }
            }
        }
        return f[m][n];
}

public class Solution {
    public int numDistinct(String S, String T) {
        if (S==null || T==null || S.length() < T.length()) return 0;
        int[] res = new int[T.length()+1];
        res[0] = 1;
        for (int i=1; i<=S.length(); i++) {
            for (int j=T.length(); j>0; j--) {
                res[j] = S.charAt(i-1) == T.charAt(j-1)? res[j-1] + res[j] : res[j];
            }
        }
        return res[T.length()];
    }
}