#115 Distinct Subsequences
frequently reported atSalesforceAmazonGoogleBloomberg
the problem
In plain words
Count the different ways to delete letters from s (possibly none) so that exactly t is left. Two ways are different if they keep a different set of positions of s. The final answer fits in a 32-bit signed integer.
in s = "rabbbit", t = "rabbit"
out 3
Drop any one of the three b's.
in s = "babgbag", t = "bag"
out 5
- 1 ≤ s.length, t.length ≤ 1000
- English letters (upper and lower case are different)
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
pattern2D DP on two strings (LCS / edit distance)
Walk through s letter by letter. Each letter is either skipped, or — if it equals the next letter of t you still need — used. Counting both choices: dp[i][j] = dp[i − 1][j] + (s[i − 1] == t[j − 1] ? dp[i − 1][j − 1] : 0).
solutions
From brute force to optimal
count(i, j) = ways to pick t[j..] out of s[i..]: skip s[i], plus use it when it equals t[j].
- j at the end of t → 1.
- Not enough letters left in s → 0.
- skip + (match ? use : 0).
Every letter of s can branch into skip and use.
Recursion depth up to the length of s.
class Solution { public int numDistinct(String s, String t) { return count(s, t, 0, 0); } /** Ways to pick t[j..] as a subsequence of s[i..]. */ private int count(String s, String t, int i, int j) { if (j == t.length()) return 1; // all of t matched: one way if (s.length() - i < t.length() - j) return 0; // not enough letters left int ways = count(s, t, i + 1, j); // skip s[i] if (s.charAt(i) == t.charAt(j)) ways += count(s, t, i + 1, j + 1); // or use it for t[j] return ways; }}(m + 1)(n + 1) states — cache them in an Integer[][] (null = unknown).
- Check, compute, store.
Each state once.
The memo + O(m) stack.
class Solution { public int numDistinct(String s, String t) { return count(s, t, 0, 0, new Integer[s.length() + 1][t.length() + 1]); // null = unknown } private int count(String s, String t, int i, int j, Integer[][] memo) { if (j == t.length()) return 1; if (s.length() - i < t.length() - j) return 0; if (memo[i][j] != null) return memo[i][j]; int ways = count(s, t, i + 1, j, memo); if (s.charAt(i) == t.charAt(j)) ways += count(s, t, i + 1, j + 1, memo); return memo[i][j] = ways; }}dp[i][j] = ways to form t[0..j) from s[0..i).
- dp[i][0] = 1 (empty t), dp[0][j] = 0 for j > 0.
- dp[i][j] = dp[i − 1][j] + (letters match ? dp[i − 1][j − 1] : 0).
- Return dp[m][n].
One addition per cell.
The table.
class Solution { public int numDistinct(String s, String t) { int m = s.length(), n = t.length(); int[][] dp = new int[m + 1][n + 1]; // dp[i][j]: ways to form t[0..j) from s[0..i) for (int i = 0; i <= m; i++) dp[i][0] = 1; // the empty t: pick nothing, one way for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = dp[i - 1][j]; // ways that never use s[i-1] if (s.charAt(i - 1) == t.charAt(j - 1)) dp[i][j] += dp[i - 1][j - 1]; // ways that use it as t[j-1] } } return dp[m][n]; }}Skip or use, cell by cell
Each cell reads up and up-left. Loop j from n down to 1 so dp[j − 1] still holds the previous row — the 0/1 knapsack trick.
- dp[0] = 1.
- For each letter c of s: for j = n down to 1: if c == t[j − 1], dp[j] += dp[j − 1].
- Return dp[n].
Same additions.
One row of n + 1 ints.
class Solution { public int numDistinct(String s, String t) { int n = t.length(); int[] dp = new int[n + 1]; // dp[j]: ways to form t[0..j) from the letters of s seen so far dp[0] = 1; for (int i = 0; i < s.length(); i++) { for (int j = n; j >= 1; j--) { // DOWNWARD, like 0/1 knapsack: each letter of s used once if (s.charAt(i) == t.charAt(j - 1)) dp[j] += dp[j - 1]; } } return dp[n]; }}in the room
How to say it in the interview
talk track
- Say the two choices for each letter of s: skip it, or use it as the next letter of t.
- Base cases: empty t → 1 way; empty s and non-empty t → 0.
- Squeeze to one row with j going DOWN — the same reason as 0/1 knapsack.
traps
- j upward in the one-row version: a single letter of s gets used twice in one subsequence.
- Middle counts can be astronomically large (C(200, 100) ≈ 9·10⁵⁸). Java's int addition wraps around, and because the DP only adds, the final value is still exact whenever the true answer fits — but never compare or take a max of middle values.
- Treating 'A' and 'a' as equal: letters are case-sensitive.
what they ask next
Follow-ups
Is t a subsequence of s at all (LC 392)?
Two pointers, O(m + n) — Is Subsequence in the Two Pointers chapter.
Count the distinct subsequences of s itself (LC 940)?
dp over positions, subtracting the count from the previous occurrence of the same letter to avoid double counting; answer mod 10⁹ + 7.
before you submit
Edge cases to test
- t longer than s → 0.
- s equals t → 1.
- Huge middle counts, answer 0: s = 200 a's, t = 100 a's + "b".
practise next
Similar problems
- #97Interleaving StringMediumin DP Patterns
- #392Is SubsequenceEasyin Two Pointers
- #1143Longest Common SubsequenceMediumin Dynamic Programming