Distinct Subsequences: the idea to remember.

The core insight

Skip the current source character, and also consume it when it matches the current target character.

Why it works

These skip and take choices are disjoint and cover all subsequences for the remaining two suffixes.

The mistake to avoid

An empty target has one match. Update suffix states in the correct direction when compressing the table.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

// Java reference adapted from neetcode-gh/leetcode (MIT).
// Skip the current source character, and also consume it when it matches the current target character.
public int numDistinct(String s, String t) {
    int n = s.length() + 1;
    int m = t.length() + 1;
    int[][] memo = new int[n][m];

    for (int[] row : memo) {
        Arrays.fill(row, -1);
    }

    return recursion(s, t, 0, 0, memo);
}

public int recursion(String s, String t, int sIdx, int tIdx, int[][] memo) {
    if (memo[sIdx][tIdx] != -1) {
        return memo[sIdx][tIdx];
    }

    if (tIdx >= t.length()) {
        return 1;
    }

    if (sIdx >= s.length()) {
        return 0;
    }

    if (t.charAt(tIdx) == s.charAt(sIdx)) {
        memo[sIdx][tIdx] =
            recursion(s, t, sIdx + 1, tIdx + 1, memo) +
            recursion(s, t, sIdx + 1, tIdx, memo);
        return memo[sIdx][tIdx];
    }

    memo[sIdx][tIdx] = recursion(s, t, sIdx + 1, tIdx, memo);
    return memo[sIdx][tIdx];
}

Java reference adapted from neetcode-gh/leetcode · MIT license

Make the next connection