Distinct Subsequences
The drill: Count the distinct ways to obtain a shorter string by deleting characters from a longer one, without reordering what's left — every deletion pattern that lands exactly on the target counts once.
Two strings arrive: a longer source and a shorter target. The task is counting how many distinct ways letters can be deleted from the source — without disturbing the order of what's left — so the remainder reads exactly like the target.
Two deletion patterns count separately whenever they keep characters from different positions in the source, even when the surviving text looks identical. A repeated letter at several source positions can each anchor its own path to the same match.
Totals can climb fast when the source repeats letters heavily, since many independent deletion paths can land on the same target text — the count of paths is what gets reported, not any single path.
- source string is typically longer than the target, sometimes by a lot
- both strings use plain letters, and lengths stay in easily workable ranges
- an empty target counts as reachable in exactly one way — deleting everything
- path counts are reported as exact integers, however large they grow
HINT 1 THE NUDGE
At the first character of the longer string you always have two options — use it or skip it — and using it is only legal when it currently matches the next needed character of the target. Where does the branching actually come from?
HINT 2 THE STRUCTURE
Recurse on a pair of positions, one per string. Skipping never moves the target position; matching (when the characters agree) advances both. What happens once the target position reaches the end of the target?
HINT 3 ONE STEP FROM THE ANSWER
dp(i, j) = dp(i+1, j) [skip] plus dp(i+1, j+1) when s[i] == t[j] [use it]. Base cases: dp(i, len(t)) = 1 for any i — the target is already fully matched — and dp(len(s), j) = 0 whenever j < len(t).
s='bab', t='ab'. dp[i][j] counts ways to match t[j:] using s[i:]. Base column j=2 (target already empty) is1 for every row.
class Solution:
def numDistinct(self, s: str, t: str) -> int:
n, m = len(s), len(t)
# dp[i][j] = ways to match t[j:] using s[i:]
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][m] = 1
for i in range(n - 1, -1, -1):
for j in range(m - 1, -1, -1):
dp[i][j] = dp[i + 1][j]
if s[i] == t[j]:
dp[i][j] += dp[i + 1][j + 1]
return dp[0][0]class Solution:
def numDistinct(self, s: str, t: str) -> int:
n, m = len(s), len(t)
def rec(i, j):
if j == m:
return 1
if i == n:
return 0
count = rec(i + 1, j) # skip s[i]
if s[i] == t[j]:
count += rec(i + 1, j + 1) # use s[i] to match t[j]
return count
return rec(0, 0)class Solution {
public int numDistinct(String s, String t) {
int n = s.length(), m = t.length();
int[][] dp = new int[n + 1][m + 1];
for (int i = 0; i <= n; i++) {
dp[i][m] = 1;
}
for (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
dp[i][j] = dp[i + 1][j];
if (s.charAt(i) == t.charAt(j)) {
dp[i][j] += dp[i + 1][j + 1];
}
}
}
return dp[0][0];
}
}class Solution {
private String s, t;
private int n, m;
public int numDistinct(String s, String t) {
this.s = s;
this.t = t;
n = s.length();
m = t.length();
return rec(0, 0);
}
private int rec(int i, int j) {
if (j == m) return 1;
if (i == n) return 0;
int count = rec(i + 1, j);
if (s.charAt(i) == t.charAt(j)) {
count += rec(i + 1, j + 1);
}
return count;
}
}✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED