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}