246. Distinct Subsequences
🔗 LeetCode Problem: 115. Distinct Subsequences
📊 Difficulty: Hard
🏷️ Topics: Dynamic Programming, String, DP - Strings
Problem Statement
Given two strings s and t, return the number of distinct subsequences of s which equals t.
The test cases are generated so that the answer fits on a 32-bit signed integer.
Example 1:
Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
Example 2:
Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from s.
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^
Constraints:
- 1 <= s.length, t.length <= 1000
- s and t consist of English letters.
🧒 Let's Build Understanding from Absolute Scratch
What Does This Problem REALLY Ask?
Forget "distinct subsequences" for a moment. Let me understand what we're doing:
Given: s = "rabbbit", t = "rabbit"
Question: In how many DIFFERENT WAYS can we form "rabbit" from "rabbbit"?
Let me try to find all ways:
Way 1: r a b b b i t
^ ^ ^ ^ → "rabbit" ✓
Pick: positions 0,1,2,5,6
Way 2: r a b b b i t
^ ^ ^ ^ → "rabbit" ✓
Pick: positions 0,1,3,5,6
Way 3: r a b b b i t
^ ^ ^ ^ → "rabbit" ✓
Pick: positions 0,1,4,5,6
Total: 3 different ways! ✓
KEY INSIGHT: We're COUNTING the number of ways! 🔑
This is NOT about matching (yes/no)
This is about COUNTING (how many)!
Understanding Subsequences
What is a subsequence?
A subsequence is formed by DELETING some (or no) characters
WITHOUT changing the order of remaining characters.
Example: s = "abc"
All subsequences:
"" (delete all)
"a" (delete b,c)
"b" (delete a,c)
"c" (delete a,b)
"ab" (delete c)
"ac" (delete b)
"bc" (delete a)
"abc" (delete nothing)
Total: 2^3 = 8 subsequences
IMPORTANT: Order is preserved!
"abc" can give "ac" (delete b)
"abc" CANNOT give "ca" (order changed!) ✗
This is KEY! 🔑
Why Is This Different From Previous Problems?
Let me compare with problems we've solved:
PROBLEM 243/244: Pattern Matching
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Question: DOES pattern match string? (YES/NO)
Answer: Boolean (true/false)
Goal: Find IF match exists
Example: "abc" matches "a*c"? → true ✓
PROBLEM 245: Edit Distance
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Question: MINIMUM operations to transform?
Answer: Integer (count of operations)
Goal: Find MINIMUM
Example: "cat" → "cut" → 1 operation ✓
PROBLEM 246: Distinct Subsequences
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Question: HOW MANY ways to form subsequence?
Answer: Integer (count of ways)
Goal: Find COUNT (not minimum, not boolean!)
Example: "rabbbit" → "rabbit" → 3 ways ✓
KEY DIFFERENCE:
Previous: Boolean or Minimum
This: COUNT all possibilities! 🔑
This is a COUNTING problem! 🎯
🤔 Building Intuition - The Counting Structure
Understanding The Counting Logic
Let me think about how counting works:
Example: s = "babgbag", t = "bag"
To form "bag", I need to find 'b', then 'a', then 'g' IN ORDER.
Let me trace manually:
Finding 'b' (first character):
Position 0: 'b' ✓
Position 2: 'b' ✓
Position 4: 'b' ✓
Three choices for first 'b'!
For EACH choice of 'b', I find 'a':
Choice 1 (b at position 0):
After position 0, find 'a':
Position 1: 'a' ✓
One choice for 'a'!
For this 'a', find 'g':
Position 3: 'g' ✓
Position 6: 'g' ✓
Two choices for 'g'!
Total for this 'b': 1 × 2 = 2 ways
Choice 2 (b at position 2):
After position 2, find 'a':
Position 5: 'a' ✓
One choice for 'a'!
For this 'a', find 'g':
Position 6: 'g' ✓
One choice for 'g'!
Total for this 'b': 1 × 1 = 1 way
Choice 3 (b at position 4):
After position 4, find 'a':
Position 5: 'a' ✓
One choice for 'a'!
For this 'a', find 'g':
Position 6: 'g' ✓
One choice for 'g'!
Total for this 'b': 1 × 1 = 1 way
But wait! Choice 2 and 3 might overlap! 🤔
Actually they use DIFFERENT 'b's, so they're DISTINCT! ✓
Total: 2 + 1 + 1 + 1 more = 5 ways ✓
INSIGHT: This is a TREE of choices!
Count ALL possible paths! 🔑
The Key Insight - Characters Match or Not
When comparing s[i] with t[j]:
CASE 1: Characters match (s[i] == t[j])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
We have TWO choices:
Choice A: USE this matching character
Match s[i] with t[j]
Continue with remaining strings
Example: s="rabbit", t="rabbit"
'r' matches 'r', use it
Continue with "abbit" vs "abbit"
Choice B: SKIP this character in s
Don't use s[i] for this match
Keep looking for another match
Example: s="rabbbit", t="rabbit"
First 'b' matches, but skip it
Use second 'b' instead
IMPORTANT: We must count BOTH choices!
Total ways = Choice A + Choice B
This is different from previous problems! 🔑
CASE 2: Characters don't match (s[i] != t[j])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Only ONE choice:
Must SKIP s[i]
Keep looking in remaining s for t[j]
Example: s="abc", t="b"
'a' != 'b', skip 'a'
Continue with "bc" vs "b"
No other option! ✓
Why This Makes Sense - The Counting Logic
Let me verify this with example:
s = "rabbbit", t = "rabbit"
At first 'b' in s:
s = "rab b bit", t = "rabbit"
^
s[3]='b', t[2]='b' → Match!
Choice A: USE this 'b'
Ways using this 'b' = ways to form "bit" from "bit" = 1
Choice B: SKIP this 'b'
Ways skipping this 'b' = ways to form "rabbit" from "rabbit"
= ways using OTHER 'b's = 2
Total: 1 + 2 = 3 ✓
This explains why we ADD both choices!
If we DON'T match:
s = "abc", t = "d"
'a' != 'd'
Can't use 'a' → skip it!
Ways = ways to form "d" from "bc" = 0
Only one choice when no match! ✓
💡 The Recursive Structure
Defining The Recursive Function
Define: numDistinct(i, j) = number of ways to form t[j..]
using subsequence of s[i..]
What this means:
- s[i..] is substring of s starting from index i
- t[j..] is substring of t starting from index j
- Return count of distinct ways
Base cases:
BASE CASE 1: Target exhausted (j == len(t))
We've formed the complete target string!
This is ONE valid way!
return 1 ✓
Example: s="abc", t=""
Already formed "" → 1 way
BASE CASE 2: Source exhausted (i == len(s))
Source is empty but target has characters
Can't form target!
return 0 ✗
Example: s="", t="a"
Can't form "a" from "" → 0 ways
Recursive cases:
CASE 1: Characters match (s[i] == t[j])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Two choices:
Choice A: USE this matching character
numDistinct(i+1, j+1)
Move both pointers forward
Choice B: SKIP this character in s
numDistinct(i+1, j)
Move only s pointer forward
Total: numDistinct(i, j) = Choice A + Choice B
= numDistinct(i+1, j+1) + numDistinct(i+1, j)
CASE 2: Characters don't match (s[i] != t[j])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
One choice:
SKIP s[i]
numDistinct(i, j) = numDistinct(i+1, j)
This is the complete recursive structure! ✓
Visualizing The Recursion - Small Example
Example: s = "bag", t = "bag"
numDistinct(0,0)
s[0]='b', t[0]='b' → Match!
USE or SKIP?
USE: numDistinct(1,1) SKIP: numDistinct(1,0)
s[1]='a', t[1]='a' s[1]='a', t[0]='b'
Match! No match!
USE(2,2) SKIP(2,1) SKIP: numDistinct(2,0)
s[2]='g' s[2]='g' s[2]='g', t[0]='b'
t[2]='g' t[1]='a' No match!
Match! No match!
USE(3,3) SKIP(3,1) SKIP(3,0)
Base! s="" s="", t[0]='b'
return 1 t="ag" return 0
return 0
Total: 1 0 0
Left path: 1 + 0 = 1
Right path: 0
Total: 1 + 0 = 1 way ✓
Makes sense! Only one way to form "bag" from "bag"!
Another example: s = "abb", t = "ab"
Can form "ab" by:
1. Use first 'a', use first 'b' → "ab"
2. Use first 'a', use second 'b' → "ab"
Total: 2 ways ✓
The recursion tree counts all these! ✓
🔴 Approach 1: Pure Recursion - Understanding the Pattern
The Recursive Logic
Let me write the recursive function:
numDistinct(s, t, i, j):
BASE CASE 1: Target exhausted
if j == len(t):
return 1 // Formed complete target!
BASE CASE 2: Source exhausted
if i == len(s):
return 0 // Can't form remaining target
RECURSIVE CASE 1: Characters match
if s[i] == t[j]:
// Choice A: Use this character
useIt = numDistinct(i+1, j+1)
// Choice B: Skip this character
skipIt = numDistinct(i+1, j)
return useIt + skipIt
RECURSIVE CASE 2: Characters don't match
else:
// Only choice: Skip
return numDistinct(i+1, j)
This is the complete algorithm! ✓
Implementation
class Solution {
public int numDistinct(String s, String t) {
return numDistinctHelper(s, t, 0, 0);
}
private int numDistinctHelper(String s, String t, int i, int j) {
// Base case: target exhausted
if (j == t.length()) {
return 1;
}
// Base case: source exhausted
if (i == s.length()) {
return 0;
}
int count = 0;
// Case 1: Characters match
if (s.charAt(i) == t.charAt(j)) {
// Choice A: Use this character
count += numDistinctHelper(s, t, i + 1, j + 1);
// Choice B: Skip this character
count += numDistinctHelper(s, t, i + 1, j);
}
// Case 2: Characters don't match
else {
// Skip this character
count += numDistinctHelper(s, t, i + 1, j);
}
return count;
}
}
Why This Is Too Slow
TIME COMPLEXITY ANALYSIS:
At each matching position, we make 2 recursive calls!
Recursion tree branches exponentially!
(0,0)
/ \
(1,1) (1,0)
/ \ / \
(2,2)(2,1)(2,1)(2,0)
↑ ↑
SAME STATE called TWICE!
Number of unique states: m × n
But each state called MANY times!
Worst case: O(2^m) ❌
For s = "aaaaaaaaaa" (10 'a's)
t = "aaaaa" (5 'a's)
Each 'a' in s can match any 'a' in t
Huge number of paths!
2^10 = 1024 branches! ❌
OBSERVATION:
Same (i,j) computed multiple times!
Overlapping subproblems!
This screams MEMOIZATION! 🔑
🟡 Approach 2: Memoization (Top-Down DP)
Adding The Cache
The problem with pure recursion:
We solve same (i,j) many times!
Solution:
Cache the results!
memo[i][j] = count for numDistinct(i, j)
When we compute numDistinct(i, j):
1. Check if already computed (in memo)
2. If yes, return cached result (O(1)!)
3. If no, compute it, cache it, then return
This eliminates redundant computation! ✓
Why this works:
- Number of states: m × n
- Each state computed AT MOST once
- Total time: O(m × n) ✓
Much better than exponential! 🚀
Implementation
class Solution {
private Integer[][] memo;
public int numDistinct(String s, String t) {
// Initialize memoization table
memo = new Integer[s.length() + 1][t.length() + 1];
return numDistinctHelper(s, t, 0, 0);
}
private int numDistinctHelper(String s, String t, int i, int j) {
// Check memo first
if (memo[i][j] != null) {
return memo[i][j];
}
// Base case: target exhausted
if (j == t.length()) {
memo[i][j] = 1;
return 1;
}
// Base case: source exhausted
if (i == s.length()) {
memo[i][j] = 0;
return 0;
}
int count = 0;
// Case 1: Characters match
if (s.charAt(i) == t.charAt(j)) {
// Choice A: Use this character
count += numDistinctHelper(s, t, i + 1, j + 1);
// Choice B: Skip this character
count += numDistinctHelper(s, t, i + 1, j);
}
// Case 2: Characters don't match
else {
// Skip this character
count += numDistinctHelper(s, t, i + 1, j);
}
// Cache the result
memo[i][j] = count;
return count;
}
}
Why Memoization Works
KEY INSIGHT:
Number of unique states: m × n
(m = length of s, n = length of t)
Each state computed AT MOST ONCE!
When we see same (i,j) again:
Return cached result in O(1)!
TIME COMPLEXITY:
Number of states: O(m × n)
Work per state: O(1) operations
Total: O(m × n) ✓
SPACE COMPLEXITY:
Memo table: O(m × n)
Call stack: O(m + n)
Total: O(m × n) ✓
Much better than O(2^m)! 🚀
🟢 Approach 3: Bottom-Up DP - Building From Base Cases
Understanding The DP State
Let me think about the DP table:
dp[i][j] = number of ways to form t[0..j-1]
using subsequence of s[0..i-1]
What this means:
- s[0..i-1] means first i characters of s
- t[0..j-1] means first j characters of t
- dp[i][j] answers: count of distinct ways
Examples:
s = "bag", t = "bag"
dp[0][0] = form "" from "" → 1 way ✓
dp[1][1] = form "b" from "b" → 1 way ✓
dp[2][2] = form "ba" from "ba" → 1 way ✓
dp[3][3] = form "bag" from "bag" → (final answer)
This is our DP definition! ✓
Building The DP Table - Understanding Each Cell
Let me build for: s = "bag", t = "bag"
Table dimensions: (len(s)+1) × (len(t)+1) = 4 × 4
Initial state:
"" b a g
"" ? ? ? ?
b ? ? ? ?
a ? ? ? ?
g ? ? ? ?
PHASE 1: Base Cases
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[i][0]: Form "" (empty target) from any prefix
Empty target can be formed by DELETING all!
Always ONE way! ✓
dp[0][0] = 1 (delete nothing)
dp[1][0] = 1 (delete 'b')
dp[2][0] = 1 (delete "ba")
dp[3][0] = 1 (delete "bag")
"" b a g
"" 1 ? ? ?
b 1 ? ? ?
a 1 ? ? ?
g 1 ? ? ?
dp[0][j]: Form t[0..j-1] from "" (empty source)
Can't form anything from empty!
Always ZERO ways! ✗
dp[0][1] = 0 (can't form "b")
dp[0][2] = 0 (can't form "ba")
dp[0][3] = 0 (can't form "bag")
"" b a g
"" 1 0 0 0
b 1 ? ? ?
a 1 ? ? ?
g 1 ? ? ?
PHASE 2: Fill The Table
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[1][1]: Form "b" from "b"
s[0]='b', t[0]='b' → Match! ✓
Two choices:
Use this 'b': dp[0][0] = 1
Skip this 'b': dp[0][1] = 0
Total: 1 + 0 = 1 way
"" b a g
"" 1 0 0 0
b 1 1 ? ?
a 1 ? ? ?
g 1 ? ? ?
dp[1][2]: Form "ba" from "b"
s[0]='b', t[1]='a' → Don't match ✗
Only choice:
Skip 'b': dp[0][2] = 0
Total: 0 ways
"" b a g
"" 1 0 0 0
b 1 1 0 ?
a 1 ? ? ?
g 1 ? ? ?
dp[1][3]: Form "bag" from "b"
Can't form "bag" from "b"
Total: 0 ways
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 ? ? ?
g 1 ? ? ?
dp[2][1]: Form "b" from "ba"
s[1]='a', t[0]='b' → Don't match ✗
Skip 'a': dp[1][1] = 1
Total: 1 way
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 1 ? ?
g 1 ? ? ?
dp[2][2]: Form "ba" from "ba"
s[1]='a', t[1]='a' → Match! ✓
Two choices:
Use this 'a': dp[1][1] = 1
Skip this 'a': dp[1][2] = 0
Total: 1 + 0 = 1 way
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 1 1 ?
g 1 ? ? ?
dp[2][3]: Form "bag" from "ba"
s[1]='a', t[2]='g' → Don't match ✗
Skip 'a': dp[1][3] = 0
Total: 0 ways
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 1 1 0
g 1 ? ? ?
dp[3][1]: Form "b" from "bag"
s[2]='g', t[0]='b' → Don't match ✗
Skip 'g': dp[2][1] = 1
Total: 1 way
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 1 1 0
g 1 1 ? ?
dp[3][2]: Form "ba" from "bag"
s[2]='g', t[1]='a' → Don't match ✗
Skip 'g': dp[2][2] = 1
Total: 1 way
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 1 1 0
g 1 1 1 ?
dp[3][3]: Form "bag" from "bag"
s[2]='g', t[2]='g' → Match! ✓
Two choices:
Use this 'g': dp[2][2] = 1
Skip this 'g': dp[2][3] = 0
Total: 1 + 0 = 1 way
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 1 1 0
g 1 1 1 1
FINAL ANSWER: dp[3][3] = 1 ✓
Only 1 way to form "bag" from "bag"! ✓
More Interesting Example
Let me build for: s = "rabbbit", t = "rabbit"
This will show multiple ways!
Table dimensions: 8 × 7
Key cells:
dp[0][0] = 1 (empty to empty)
First row: dp[0][j] = 0 for all j > 0
First column: dp[i][0] = 1 for all i
After filling (I'll skip intermediate steps):
"" r a b b i t
"" 1 0 0 0 0 0 0
r 1 1 0 0 0 0 0
a 1 1 1 0 0 0 0
b 1 1 1 1 0 0 0
b 1 1 1 2 1 0 0
b 1 1 1 3 3 0 0
i 1 1 1 3 3 3 0
t 1 1 1 3 3 3 3
Key observation at dp[5][3] = 3:
Form "rab" from "rabbb"
Three 'b's in source, one 'b' needed
Three ways to choose which 'b'!
FINAL ANSWER: dp[7][6] = 3 ✓
Three ways to form "rabbit" from "rabbbit"! ✓
The DP Recurrence - Complete Understanding
For dp[i][j], we're asking:
Number of ways to form t[0..j-1] using s[0..i-1]?
CASE 1: Target is empty (j == 0)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[i][0] = 1 for all i
One way to form empty string: delete everything!
CASE 2: Source is empty (i == 0)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[0][j] = 0 for all j > 0
Can't form non-empty string from empty source!
CASE 3: Characters match (s[i-1] == t[j-1])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Two choices:
Choice A: USE this matching character
Count ways if we use it
dp[i-1][j-1]
Example: "rab" vs "rab"
Use last 'b' → count "ra" vs "ra"
Choice B: SKIP this character in s
Count ways if we don't use it
dp[i-1][j]
Example: "rabbb" vs "rab"
Skip last 'b' → count "rabb" vs "rab"
Total: dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
CASE 4: Characters don't match (s[i-1] != t[j-1])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
One choice:
Must SKIP s[i-1]
dp[i][j] = dp[i-1][j]
Example: "abc" vs "d"
'c' != 'd' → skip 'c' → count "ab" vs "d"
This is the complete DP recurrence! ✓
Why Forward Loops?
DEPENDENCY ANALYSIS:
dp[i][j] depends on:
- dp[i-1][j-1] (diagonal - one less from both)
- dp[i-1][j] (up - one less from source)
All dependencies have SMALLER indices!
Visual:
j-1 j
i-1 [X] [X]
↘ ↓
i [i,j]
All arrows point to smaller indices!
Therefore: Fill table with FORWARD loops!
for i from 0 to m:
for j from 0 to n:
compute dp[i][j]
Dependencies are already computed! ✓
Complete Implementation
class Solution {
public int numDistinct(String s, String t) {
int m = s.length();
int n = t.length();
// dp[i][j] = ways to form t[0..j-1] from s[0..i-1]
int[][] dp = new int[m + 1][n + 1];
// Base case: empty target can be formed by deleting all
for (int i = 0; i <= m; i++) {
dp[i][0] = 1;
}
// Base case: can't form non-empty target from empty source
// (already 0 by default)
// Fill the table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
// Characters match - two choices
// Choice A: Use this character
// Choice B: Skip this character
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
// Characters don't match - skip this character
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[m][n];
}
}
🔍 Detailed Example - Complete Walkthrough
Example: s = "babgbag", t = "bag"
Let me build the complete DP table!
m = 7 (babgbag), n = 3 (bag)
Table dimensions: 8 × 4
PHASE 1: Initialize Base Cases
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
"" b a g
"" 1 0 0 0
b 1 ? ? ?
a 1 ? ? ?
b 1 ? ? ?
g 1 ? ? ?
b 1 ? ? ?
a 1 ? ? ?
g 1 ? ? ?
PHASE 2: Fill Row By Row
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ROW 1 (i=1, s[0]='b'):
dp[1][1]: 'b' vs 'b' → Match!
Use: dp[0][0] = 1
Skip: dp[0][1] = 0
Total: 1 + 0 = 1
dp[1][2]: 'b' vs 'a' → No match
Skip: dp[0][2] = 0
Total: 0
dp[1][3]: 'b' vs 'g' → No match
Skip: dp[0][3] = 0
Total: 0
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 ? ? ?
b 1 ? ? ?
g 1 ? ? ?
b 1 ? ? ?
a 1 ? ? ?
g 1 ? ? ?
ROW 2 (i=2, s[1]='a'):
dp[2][1]: 'a' vs 'b' → No match
Skip: dp[1][1] = 1
Total: 1
dp[2][2]: 'a' vs 'a' → Match!
Use: dp[1][1] = 1
Skip: dp[1][2] = 0
Total: 1 + 0 = 1
dp[2][3]: 'a' vs 'g' → No match
Skip: dp[1][3] = 0
Total: 0
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 1 1 0
b 1 ? ? ?
g 1 ? ? ?
b 1 ? ? ?
a 1 ? ? ?
g 1 ? ? ?
ROW 3 (i=3, s[2]='b'):
dp[3][1]: 'b' vs 'b' → Match!
Use: dp[2][0] = 1
Skip: dp[2][1] = 1
Total: 1 + 1 = 2 ← Two ways now!
dp[3][2]: 'b' vs 'a' → No match
Skip: dp[2][2] = 1
Total: 1
dp[3][3]: 'b' vs 'g' → No match
Skip: dp[2][3] = 0
Total: 0
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 1 1 0
b 1 2 1 0
g 1 ? ? ?
b 1 ? ? ?
a 1 ? ? ?
g 1 ? ? ?
ROW 4 (i=4, s[3]='g'):
dp[4][1]: 'g' vs 'b' → No match
Skip: dp[3][1] = 2
Total: 2
dp[4][2]: 'g' vs 'a' → No match
Skip: dp[3][2] = 1
Total: 1
dp[4][3]: 'g' vs 'g' → Match!
Use: dp[3][2] = 1
Skip: dp[3][3] = 0
Total: 1 + 0 = 1 ← First complete way!
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 1 1 0
b 1 2 1 0
g 1 2 1 1
b 1 ? ? ?
a 1 ? ? ?
g 1 ? ? ?
ROW 5 (i=5, s[4]='b'):
dp[5][1]: 'b' vs 'b' → Match!
Use: dp[4][0] = 1
Skip: dp[4][1] = 2
Total: 1 + 2 = 3 ← Three 'b's seen!
dp[5][2]: 'b' vs 'a' → No match
Skip: dp[4][2] = 1
Total: 1
dp[5][3]: 'b' vs 'g' → No match
Skip: dp[4][3] = 1
Total: 1
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 1 1 0
b 1 2 1 0
g 1 2 1 1
b 1 3 1 1
a 1 ? ? ?
g 1 ? ? ?
ROW 6 (i=6, s[5]='a'):
dp[6][1]: 'a' vs 'b' → No match
Skip: dp[5][1] = 3
Total: 3
dp[6][2]: 'a' vs 'a' → Match!
Use: dp[5][1] = 3
Skip: dp[5][2] = 1
Total: 3 + 1 = 4 ← Growing!
dp[6][3]: 'a' vs 'g' → No match
Skip: dp[5][3] = 1
Total: 1
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 1 1 0
b 1 2 1 0
g 1 2 1 1
b 1 3 1 1
a 1 3 4 1
g 1 ? ? ?
ROW 7 (i=7, s[6]='g'):
dp[7][1]: 'g' vs 'b' → No match
Skip: dp[6][1] = 3
Total: 3
dp[7][2]: 'g' vs 'a' → No match
Skip: dp[6][2] = 4
Total: 4
dp[7][3]: 'g' vs 'g' → Match!
Use: dp[6][2] = 4
Skip: dp[6][3] = 1
Total: 4 + 1 = 5 ✓
"" b a g
"" 1 0 0 0
b 1 1 0 0
a 1 1 1 0
b 1 2 1 0
g 1 2 1 1
b 1 3 1 1
a 1 3 4 1
g 1 3 4 5
FINAL ANSWER: dp[7][3] = 5 ✓
Five ways to form "bag" from "babgbag"!
The five ways are:
1. b a b g b a g (positions 0,1,3)
^ ^ ^
2. b a b g b a g (positions 0,1,6)
^ ^ ^
3. b a b g b a g (positions 0,5,3)
^ ^ ^
4. b a b g b a g (positions 0,5,6)
^ ^ ^
5. b a b g b a g (positions 2,5,3 or 2,5,6)
^ ^ ^
📊 Complexity Analysis
All Approaches Compared
┌──────────────┬─────────────┬──────────────┬──────────────┐
│ Approach │ Time │ Space │ Practical? │
├──────────────┼─────────────┼──────────────┼──────────────┤
│ Recursion │ O(2^m) │ O(m+n) │ NO ❌ │
│ (Approach 1) │ Exponential │ Stack │ Too slow │
├──────────────┼─────────────┼──────────────┼──────────────┤
│ Memoization │ O(m×n) │ O(m×n) │ YES ✓ │
│ (Approach 2) │ Polynomial │ Memo+Stack │ Good │
├──────────────┼─────────────┼──────────────┼──────────────┤
│ Bottom-Up DP │ O(m×n) │ O(m×n) │ YES ✓ │
│ (Approach 3) │ Polynomial │ Table only │ Best │
└──────────────┴─────────────┴──────────────┴──────────────┘
m = length of s (source)
n = length of t (target)
Detailed Time Complexity
APPROACH 1 - Pure Recursion:
At each matching position:
Two choices (use or skip)
Two recursive calls
Worst case: All characters match
Every position branches into 2
Branching factor: 2
Tree height: m (source length)
Total nodes: O(2^m) ❌
For s = "aaaaaaaaaa" (10 'a's)
t = "aaaaa" (5 'a's)
2^10 = 1024 branches! ❌
APPROACH 2 - Memoization:
Number of unique states: m × n
Each state computed once: O(1) work
Total: O(m × n) ✓
For s = 100 chars, t = 50 chars:
100 × 50 = 5,000 states ✓
APPROACH 3 - Bottom-Up DP:
Nested loops: i from 0 to m, j from 0 to n
Each cell: O(1) work (one or two additions)
Total: O(m × n) ✓
Same as memoization! ✓
Detailed Space Complexity
APPROACH 1 - Pure Recursion:
Call stack depth: O(m + n)
No extra storage
Total: O(m + n)
But impractical due to time! ❌
APPROACH 2 - Memoization:
Memo table: (m+1) × (n+1) integers
Size: O(m × n)
Call stack: O(m + n)
Total: O(m × n) ✓
APPROACH 3 - Bottom-Up DP:
DP table: (m+1) × (n+1) integers
Size: O(m × n)
No recursion stack!
Total: O(m × n) ✓
SPACE OPTIMIZATION:
Can we use O(n) space?
YES! Only need previous row!
int[] prev = new int[n+1];
int[] curr = new int[n+1];
For each i:
Compute curr from prev
prev = curr
Space: O(n) ✓
Since we only look at dp[i-1][j-1] and dp[i-1][j]!
🎯 Pattern Recognition
Counting vs Boolean vs Minimum
STRING DP PROBLEM TYPES:
TYPE 1: BOOLEAN (Yes/No)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Question: Does X match Y?
Answer: true/false
Example: Pattern matching (243, 244)
Recurrence:
dp[i][j] = (condition) ? true : false
Combine with OR: dp[i][j] = optionA || optionB
TYPE 2: MINIMUM (Optimization)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Question: What's minimum cost?
Answer: integer (count)
Example: Edit distance (245)
Recurrence:
dp[i][j] = cost + subproblem
Combine with MIN: dp[i][j] = min(optionA, optionB)
TYPE 3: COUNTING (Combinatorics)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Question: How many ways?
Answer: integer (count)
Example: Distinct subsequences (246) ← THIS!
Recurrence:
dp[i][j] = count from subproblem
Combine with SUM: dp[i][j] = optionA + optionB
KEY DIFFERENCE:
Boolean: OR (any path works)
Minimum: MIN (best path)
Counting: SUM (all paths) 🔑
This changes EVERYTHING! ✓
The Subsequence Problem Family
SUBSEQUENCE PROBLEMS:
1. Longest Common Subsequence (241):
Question: Length of longest common?
Type: Maximum (optimization)
2. Delete Operations (239):
Question: Min deletions to make equal?
Type: Minimum (optimization)
Uses LCS!
3. Distinct Subsequences (246):
Question: How many ways?
Type: Counting! ← THIS!
4. Is Subsequence (392):
Question: Is t subsequence of s?
Type: Boolean
5. Shortest Common Supersequence (240):
Question: Shortest containing both?
Type: Construction
Uses LCS!
Common pattern:
- Subsequence relationship
- Character matching
- DP solution
- O(m × n) complexity
But DIFFERENT question types! 🔑
When To Recognize This Pattern
TRIGGER WORDS:
✓ "Number of ways"
✓ "How many"
✓ "Count distinct"
✓ "Subsequence"
✓ "Form target from source"
PROBLEM STRUCTURE:
- Two strings
- Subsequence relationship
- Count all possibilities
- Not minimum/maximum
SOLUTION APPROACH:
1. Define counting state: dp[i][j]
2. Base cases: empty strings
3. Recurrence: match → ADD both choices
4. Fill table forward
5. Return dp[m][n]
KEY INSIGHT:
When characters match, we ADD both choices!
This counts ALL paths, not just best! 🔑
💻 Complete Working Code
class Solution {
// Approach 3: Bottom-Up DP (Most efficient)
public int numDistinct(String s, String t) {
int m = s.length();
int n = t.length();
int[][] dp = new int[m + 1][n + 1];
// Base case: empty target
for (int i = 0; i <= m; i++) {
dp[i][0] = 1;
}
// Fill table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
// Match - two choices
// Use this char + Skip this char
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
// No match - skip this char
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[m][n];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.numDistinct("rabbbit", "rabbit")); // 3
System.out.println(sol.numDistinct("babgbag", "bag")); // 5
System.out.println(sol.numDistinct("bag", "bag")); // 1
}
}
🔑 Key Insights Summary
The Learning Journey
CRAWL (Understanding):
✓ What is a subsequence?
✓ Why counting (not boolean/minimum)?
✓ Understanding the choices
✓ Two choices when match!
WALK (Building):
✓ Recursive structure
✓ Base cases (empty strings)
✓ Two cases (match vs no match)
✓ Why ADD (not OR or MIN)
RUN (Mastery):
✓ Bottom-up DP
✓ Complete table construction
✓ Cell-by-cell understanding
✓ Pattern recognition
✓ Counting vs other types
Natural baby-to-expert progression! 🎯
The Core Understanding
1. WHY counting?
Want ALL ways, not just one!
Count every valid path!
2. WHAT changes from other problems?
Match: ADD both choices (use + skip)
Previous: OR or MIN
3. HOW to count?
dp[i][j] = sum of all paths
Each path is independent!
4. WHEN do we add?
When characters match!
Two choices both valid!
5. WHERE to look?
dp[i-1][j-1] (use)
dp[i-1][j] (skip)
SUM them!
Mental Model
Think of it as TREE of CHOICES:
Each matching character creates branch:
Left: Use this character
Right: Skip this character
Both branches count!
Count ALL paths from root to leaves! ✓
Visual:
start
/ \
use skip
/ \ / \
use skip use skip
Count ALL leaf nodes! ✓
This is why we ADD, not MIN/OR! 🔑
📝 Quick Revision
🎯 Core Concept
COUNTING problem → ADD choices
NOT minimum → NOT Boolean
⚡ Quick Implementation
public class Solution {
public int numDistinct(String s, String t) {
// return recursive(s, t, 0, 0);
// Integer[][] memo = new Integer[s.length() + 1][t.length() + 1];
// return topDown(s, t, 0, 0, memo);
return bottomUp(s, t);
}
private int bottomUp(String s, String t) {
int[][] dp = new int[s.length() + 1][t.length() + 1];
// step 1: base case 1
// Form "" (empty target) from any prefix
for (int i = 0; i <= s.length(); i++) {
dp[i][0] = 1;
}
// same steps as recursive or top down
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= t.length(); j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
int useIt = dp[i - 1][j - 1];
int skipIt = dp[i - 1][j];
dp[i][j] = useIt + skipIt;
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[s.length()][t.length()];
}
private int topDown(String s, String t, int i, int j, Integer[][] memo) {
if (j == t.length()) {
return 1;
}
if (i == s.length()) {
return 0;
}
if (memo[i][j] != null) {
return memo[i][j];
}
if (s.charAt(i) == t.charAt(j)) {
int useIt = topDown(s, t, i + 1, j + 1, memo);
int skipIt = topDown(s, t, i + 1, j, memo);
return memo[i][j] = useIt + skipIt;
}
return memo[i][j] = topDown(s, t, i + 1, j, memo);
}
private int recursive(String s, String t, int i, int j) {
// step 3: base case 1 - second word exhausted
if (j == t.length()) {
return 1;
}
// step 4: base case 2 - first word exhausted
if (i == s.length()) {
return 0;
}
// step 1: if chars match
if (s.charAt(i) == t.charAt(j)) {
// step 1a: use it - consider it and go for next char match
int useIt = recursive(s, t, i + 1, j + 1);
// step 1b: skip it - do not consider it
int skipIt = recursive(s, t, i + 1, j);
return useIt + skipIt;
}
// step 2: if chars do not match - skip it to match for next char
return recursive(s, t, i + 1, j);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.numDistinct("rabbbit", "rabbit") == 3);
System.out.println(s.numDistinct("babgbag", "bag") == 5);
}
}
🎪 Memory Aid
"Counting means ADD"
"Match gives two ways"
"Sum all the paths"
Complexity: O(m×n) time and space
🎉 Congratulations!
You've mastered through baby steps: - ✅ CRAWL: Understanding counting problems - ✅ WALK: Building recursive structure - ✅ RUN: Complete DP mastery - ✅ All three approaches explained - ✅ Complete table walkthrough - ✅ Understanding COUNT vs MIN vs BOOLEAN - ✅ Pattern recognition mastery - ✅ True comprehensive understanding
You've learned the KEY difference between problem types with textbook-style learning! 🚀✨