Distinct Subsequences
Solve this Problems and t, count how many distinct ways there are to pick a subset of positions in s (keeping their original order) so that the characters at those positions spell out t exactly. Two ways are different if they use a different set of positions from s, even when the resulting characters look identical (repeated letters matter).
Every matched position in s either gets used to satisfy the next needed character of t or gets skipped, so this is a natural fit for tracking, at every prefix-length pair (i, j), how many ways there are to have already matched the first j characters of t using only the first i characters of s. That count always carries forward everything a shorter prefix of s already achieved (skipping s[i-1] changes nothing), and — only when s[i-1] happens to equal the character t is currently waiting on — picks up one more source of matches: every way the previous state matched one character less. Chaining that rule across the whole grid turns an exponential search into a single pass over an (n+1)×(m+1) table.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ s.length, t.length ≤ 10 - ◆
s and t consist of lowercase English letters - ◆
the answer is guaranteed to fit in a 32-bit signed integer for the given ranges
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Recursive Without Memoization
BruteWalk both strings from left to right with two pointers, i into s and j into t. At every position there are always two things you could do with the current character of s: skip it, or — only when it matches the current character of t — use it to satisfy that character of t and move both pointers forward. Trying both choices whenever they're both legal, and just skipping when they're not, explores every way s's characters could be picked out to spell t; a full match happens exactly when the t-pointer has walked off the end. Without caching, the same (i, j) pair gets recomputed many times, which is where the exponential blow-up comes from.
O(2ⁿ)O(n)1class Solution {
2 public int numDistinct(String s, String t) {
3 return helper(s, t, 0, 0);
4 }
5 private int helper(String s, String t, int i, int j) {
6 if (j == t.length()) return 1;
7 if (i == s.length()) return 0;
8 int count = helper(s, t, i + 1, j);
9 if (s.charAt(i) == t.charAt(j)) {
10 count += helper(s, t, i + 1, j + 1);
11 }
12 return count;
13 }
14}Bottom-Up Dynamic Programming (Tabulation)
OptimalTurn the same two-pointer recursion into a table dp[i][j] = number of ways the first i characters of s can spell out the first j characters of t. The whole first column is 1: an empty target is always matched exactly once, by picking nothing. From there, dp[i][j] always inherits dp[i-1][j] — every way to build t[0..j) from a shorter prefix of s is still valid — and, only when s[i-1] equals t[j-1], also picks up dp[i-1][j-1] on top, since that shared character can additionally be used to close out one more matched position. Filling the table row by row turns every repeated subproblem from the recursive version into a single lookup, and the answer sits in the bottom-right corner.
O(n·m)O(n·m)1class Solution {
2 public int numDistinct(String s, String t) {
3 int n = s.length(), m = t.length();
4 int[][] dp = new int[n + 1][m + 1];
5 for (int i = 0; i <= n; i++) dp[i][0] = 1;
6 for (int i = 1; i <= n; i++) {
7 for (int j = 1; j <= m; j++) {
8 dp[i][j] = dp[i - 1][j];
9 if (s.charAt(i - 1) == t.charAt(j - 1)) {
10 dp[i][j] += dp[i - 1][j - 1];
11 }
12 }
13 }
14 return dp[n][m];
15 }
16}