Distinct Subsequences

• Define a recursive function solve(s, t, i, j).
• Base Case 1: If j equals the length of t, it means we have successfully formed t. Return 1.
• Base Case 2: If i equals the length of s but j is less than the length of t, it's impossible to form t. Return 0.
• If s.charAt(i) is equal to t.charAt(j), the result is the sum of two recursive calls: solve(s, t, i + 1, j + 1) (matching the characters) and solve(s, t, i + 1, j) (skipping s.charAt(i)).
• If s.charAt(i) is not equal to t.charAt(j), we must skip s.charAt(i). The result is solve(s, t, i + 1, j).

The core idea is to explore all possibilities. For each character s[i] in the source string s, we compare it with the character t[j] in the target string t.

• If s[i] matches t[j], we have two choices:

  1. We can use s[i] to form the subsequence. In this case, we need to find the number of ways to form the rest of t (i.e., t[j+1:]) from the rest of s (i.e., s[i+1:]).
  2. We can skip s[i] and try to find a match for t[j] later in s. In this case, we need to find the number of ways to form t[j:] from s[i+1:]. The total number of ways is the sum of these two possibilities.

• If s[i] does not match t[j], we have no choice but to skip s[i] and try to find a match for t[j] in the rest of s (i.e., s[i+1:]).

This logic is implemented recursively. The base cases for the recursion are:

1. If we have successfully matched all characters of t (i.e., j reaches the end of t), we have found one valid subsequence. We return 1.
2. If we have run out of characters in s (i.e., i reaches the end of s) but still have characters in t to match, it's impossible to form the subsequence. We return 0.

1class Solution {2    public int numDistinct(String s, String t) {3        return solve(s, t, 0, 0);4    }5 6    private int solve(String s, String t, int i, int j) {7        // Base case 1: If we have found all characters of t, it's a valid subsequence.8        if (j == t.length()) {9            return 1;10        }11        // Base case 2: If we have run out of characters in s but not in t.12        if (i == s.length()) {13            return 0;14        }15 16        // If characters match, we have two options:17        // 1. Match s[i] with t[j] and look for the rest of t in the rest of s.18        // 2. Skip s[i] and look for t[j] in the rest of s.19        if (s.charAt(i) == t.charAt(j)) {20            return solve(s, t, i + 1, j + 1) + solve(s, t, i + 1, j);21        } else {22            // If characters don't match, we must skip s[i].23            return solve(s, t, i + 1, j);24        }25    }26}

• Create a 2D array memo of size s.length() x t.length() to store results of subproblems, initialized to a value indicating 'not computed' (e.g., null or -1).
• Modify the recursive function solve(s, t, i, j, memo).
• Inside the function, first check if memo[i][j] has been computed. If yes, return the stored value.
• If not, compute the result using the same recursive logic as the brute-force approach.
• Store the computed result in memo[i][j] before returning it.

We use a 2D array, let's call it memo, to store the results of the subproblems. memo[i][j] will store the result of solve(i, j). Before making a recursive call, we first check if the result for the current state (i, j) is already in our memoization table. If it is, we simply return the stored value. Otherwise, we compute the result as in the brute-force approach and store it in the table before returning.

This ensures that each subproblem (i, j) is solved only once. The number of unique subproblems is m * n, where m is the length of s and n is the length of t.

1class Solution {2    public int numDistinct(String s, String t) {3        int m = s.length();4        int n = t.length();5        // Use Integer to easily check for null (uncomputed states)6        Integer[][] memo = new Integer[m][n];7        return solve(s, t, 0, 0, memo);8    }9 10    private int solve(String s, String t, int i, int j, Integer[][] memo) {11        // Base case 1: Found a valid subsequence.12        if (j == t.length()) {13            return 1;14        }15        // Base case 2: Ran out of characters in s.16        if (i == s.length()) {17            return 0;18        }19 20        // Check memoization table21        if (memo[i][j] != null) {22            return memo[i][j];23        }24 25        // If characters match, we have two options.26        if (s.charAt(i) == t.charAt(j)) {27            memo[i][j] = solve(s, t, i + 1, j + 1, memo) + solve(s, t, i + 1, j, memo);28        } else {29            // If characters don't match, we must skip s[i].30            memo[i][j] = solve(s, t, i + 1, j, memo);31        }32 33        return memo[i][j];34    }35}

• Create a 2D DP table dp of size (m+1) x (n+1), where m=s.length() and n=t.length().
• Initialize the first column: dp[i][0] = 1 for all i.
• Iterate with i from 1 to m and j from 1 to n.
• If s.charAt(i-1) == t.charAt(j-1), set dp[i][j] = dp[i-1][j] + dp[i-1][j-1].
• Otherwise, set dp[i][j] = dp[i-1][j].
• The final answer is dp[m][n].

We create a 2D array dp of size (m+1) x (n+1). The extra row and column handle the base cases of empty strings.

Initialization:

• dp[i][0] = 1 for all i from 0 to m. This is because an empty string t is a subsequence of any string s in exactly one way (by deleting all characters of s).
• dp[0][j] = 0 for j > 0. A non-empty t cannot be a subsequence of an empty s.

Transitions: We iterate through the strings s and t and fill the dp table. For each dp[i][j], we consider the characters s[i-1] and t[j-1].

• If s[i-1] != t[j-1], the character s[i-1] cannot be used to form the subsequence. So, the number of ways to form t[0...j-1] from s[0...i-1] is the same as forming it from s[0...i-2]. Thus, dp[i][j] = dp[i-1][j].
• If s[i-1] == t[j-1], we have two sources for the count:
  1. Ways to form t[0...j-1] from s[0...i-2] (i.e., not using s[i-1]). This is dp[i-1][j].
  2. Ways to form t[0...j-2] from s[0...i-2] (i.e., using s[i-1] to match t[j-1]). This is dp[i-1][j-1]. So, dp[i][j] = dp[i-1][j] + dp[i-1][j-1].

The final answer is stored in dp[m][n]. We use long for the DP table to prevent potential overflow during intermediate additions, as the problem only guarantees the final answer fits in an int.

1class Solution {2    public int numDistinct(String s, String t) {3        int m = s.length();4        int n = t.length();5 6        // dp[i][j]: number of distinct subsequences of s[0..i-1] which equals t[0..j-1]7        long[][] dp = new long[m + 1][n + 1];8 9        // Base case: An empty t is a subsequence of any s in one way.10        for (int i = 0; i <= m; i++) {11            dp[i][0] = 1;12        }13 14        for (int i = 1; i <= m; i++) {15            for (int j = 1; j <= n; j++) {16                if (s.charAt(i - 1) == t.charAt(j - 1)) {17                    // Case 1: Match s[i-1] with t[j-1] -> dp[i-1][j-1]18                    // Case 2: Don't match s[i-1] with t[j-1] -> dp[i-1][j]19                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];20                } else {21                    // Must not match s[i-1]22                    dp[i][j] = dp[i - 1][j];23                }24            }25        }26 27        return (int) dp[m][n];28    }29}

• Create a 1D DP array dp of size (n+1), where n=t.length().
• Initialize dp[0] = 1.
• Iterate with an outer loop for i from 1 to m (for characters in s).
• Inside, iterate with an inner loop for j from n down to 1 (for characters in t).
• If s.charAt(i-1) == t.charAt(j-1), update dp[j] by adding dp[j-1] to it: dp[j] = dp[j] + dp[j-1].
• After the loops complete, dp[n] holds the final answer.

We can use a single 1D array, dp, of size n+1, where dp[j] will store the number of ways to form the prefix t[0...j-1].

We iterate through the characters of s one by one (from i = 1 to m). For each character s[i-1], we update the dp array. The key insight is to iterate the inner loop (for j) backwards, from n down to 1. This is crucial because when we calculate the new dp[j], we need the old dp[j] (from the previous s character) and the old dp[j-1]. By iterating backwards, dp[j-1] still holds the value from the previous outer loop iteration when we use it to update dp[j].

The transition dp[i][j] = dp[i-1][j] + dp[i-1][j-1] becomes dp[j] = dp[j] + dp[j-1] in the 1D array when s[i-1] == t[j-1].

1class Solution {2    public int numDistinct(String s, String t) {3        int m = s.length();4        int n = t.length();5 6        // dp[j] will store the number of distinct subsequences of s's prefix7        // that equals t[0..j-1].8        long[] dp = new long[n + 1];9 10        // Base case: An empty t is a subsequence of any s in one way.11        dp[0] = 1;12 13        // Iterate through s14        for (int i = 1; i <= m; i++) {15            // Iterate through t backwards16            for (int j = n; j >= 1; j--) {17                if (s.charAt(i - 1) == t.charAt(j - 1)) {18                    // dp[j] on the right is the count from the previous character of s (i-1).19                    // dp[j-1] is also the count from the previous character of s (i-1)20                    // because we are iterating j backwards.21                    dp[j] = dp[j] + dp[j - 1];22                }23            }24        }25 26        return (int) dp[n];27    }28}