101
0/276
Loading content...
How many times does the word "ace" hide within "abcde"? You might spot one: skip 'b' and 'd' to get a-c-e. But what if the source string is longer, with repeated characters? How many distinct ways can we form "rabbit" from "rabbbit"? The answer—3—isn't obvious without systematic counting.
This is the Distinct Subsequences problem: given a source string s and a target string t, count the number of distinct subsequences of s that equal t. It's a beautiful application of dynamic programming that reveals deep structure in how strings relate.
Why This Problem Matters:
Distinct subsequences appear in:
By the end of this page, you will understand the formal definition of distinct subsequences, derive the recurrence relation from first principles, implement both 2D and space-optimized 1D DP solutions, and recognize how this problem connects to other sequence counting problems.
Formal Definition:
Given strings s (source) of length n and t (target) of length m, count the number of distinct subsequences of s that equal t.
What Is a Subsequence?
A subsequence is obtained by deleting zero or more characters from a string without changing the order of remaining characters.
Distinct Subsequences:
Two subsequences are distinct if they are formed by choosing different indices, even if they result in the same string.
Example 1:
s = "rabbbit", t = "rabbit"
Distinct ways to form "rabbit":
1. ra_b_bit (skip 3rd 'b')
2. rab__bit (skip 4th 'b')
3. rab___it (skip 5th 'b')
Wait, let me recount more carefully:
s = r a b b b i t
0 1 2 3 4 5 6
To form "rabbit" (r-a-b-b-i-t), we need:
- r at index 0
- a at index 1
- b at index 2, 3, or 4 (first 'b' of "rabbit")
- b at index 3 or 4 (second 'b' of "rabbit", must be after first)
- i at index 5
- t at index 6
Combinations:
- b@2, b@3 → one way
- b@2, b@4 → one way
- b@3, b@4 → one way
Answer: 3
Example 2:
s = "babgbag", t = "bag"
We need to find all ways to form "b-a-g":
s = b a b g b a g
0 1 2 3 4 5 6
Possible subsequences forming "bag":
1. b(0) - a(1) - g(3)
2. b(0) - a(1) - g(6)
3. b(0) - a(5) - g(6)
4. b(2) - a(5) - g(6)
5. b(4) - a(5) - g(6)
Answer: 5
Key Observations:
t is longer than s, answer is 0t is empty, answer is 1 (one way to form empty subsequence)s is empty but t is not, answer is 0Don't confuse subsequence with substring. A substring is contiguous; a subsequence is not necessarily contiguous. "ace" is a subsequence of "abcde" but not a substring. "bcd" is both a substring and a subsequence of "abcde".
The key to solving this problem is finding the right recurrence relation. Let's define our DP state and derive the transitions from first principles.
DP State Definition:
Let dp[i][j] = the number of distinct subsequences of s[0..i-1] that equal t[0..j-1].
We use 1-indexed DP for cleaner base cases:
dp[i][0] for any i means: ways to form empty target from first i chars of s → always 1dp[0][j] for j > 0 means: ways to form non-empty target from empty source → always 0The Insight: What Happens at Position (i, j)?
We're at character s[i-1] in source and t[j-1] in target. Two cases:
Case 1: s[i-1] != t[j-1]
The current source character cannot match the current target character. We must skip it and look for matches in s[0..i-2].
dp[i][j] = dp[i-1][j]
Case 2: s[i-1] == t[j-1]
The characters match! We have two choices:
Use this match: We've matched t[j-1], now count ways to form t[0..j-2] from s[0..i-2] → dp[i-1][j-1]
Skip this match: Even though characters match, we might find the same target character later. Count ways to form t[0..j-1] from s[0..i-2] → dp[i-1][j]
dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
Recurrence Summary:
┌ dp[i-1][j] if s[i-1] != t[j-1]
dp[i][j] = ┤
└ dp[i-1][j-1] + dp[i-1][j] if s[i-1] == t[j-1]
Base Cases:
dp[i][0] = 1 for all i ≥ 0 (empty target: one way)
dp[0][j] = 0 for all j > 0 (empty source, non-empty target: no way)
Goal: Compute dp[n][m] where n = len(s) and m = len(t).
Visual Intuition:
Think of it as navigating a grid where rows represent characters of s and columns represent characters of t. Starting from (0, 0), we want to reach (n, m). At each step:
This is the subtle part. Even when s[i-1] == t[j-1], we count BOTH using and skipping this match. Why? Because there might be another occurrence of t[j-1] later in s that we could use instead. We're counting ALL distinct ways, not just finding one way.
Let's implement the straightforward 2D DP solution first, then optimize for space.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
def num_distinct(s: str, t: str) -> int: """ Count distinct subsequences of s that equal t. 2D Dynamic Programming Solution. Time Complexity: O(n * m) where n = len(s), m = len(t) Space Complexity: O(n * m) for the DP table Args: s: Source string t: Target string Returns: Number of distinct subsequences of s that equal t """ n, m = len(s), len(t) # Edge case: impossible if target is longer than source if m > n: return 0 # Create DP table with (n+1) x (m+1) dimensions # dp[i][j] = ways to form t[0..j-1] from s[0..i-1] dp = [[0] * (m + 1) for _ in range(n + 1)] # Base case: empty target can be formed in exactly one way for i in range(n + 1): dp[i][0] = 1 # Fill the DP table for i in range(1, n + 1): for j in range(1, m + 1): if s[i - 1] == t[j - 1]: # Characters match: use this match + skip this match dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] else: # Characters don't match: must skip source character dp[i][j] = dp[i - 1][j] return dp[n][m] def num_distinct_with_trace(s: str, t: str) -> tuple[int, list[list[int]]]: """ Same as above but returns the full DP table for visualization. """ n, m = len(s), len(t) if m > n: return 0, [] dp = [[0] * (m + 1) for _ in range(n + 1)] for i in range(n + 1): dp[i][0] = 1 for i in range(1, n + 1): for j in range(1, m + 1): if s[i - 1] == t[j - 1]: dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] else: dp[i][j] = dp[i - 1][j] return dp[n][m], dp def visualize_dp_table(s: str, t: str, dp: list[list[int]]) -> None: """ Pretty print the DP table for understanding. """ print(f"\n DP Table for s='{s}', t='{t}'") print(" ", end="") print(" ε " + " ".join(f" {c} " for c in t)) for i in range(len(dp)): char = s[i-1] if i > 0 else "ε" row_str = f"{char} " + " ".join(f"{dp[i][j]:3d}" for j in range(len(dp[0]))) print(row_str) # Demonstration with traceif __name__ == "__main__": examples = [ ("rabbbit", "rabbit"), ("babgbag", "bag"), ("abc", "abc"), ("aabb", "ab"), ] for s, t in examples: count, dp = num_distinct_with_trace(s, t) print(f"\nnum_distinct('{s}', '{t}') = {count}") if len(s) <= 10 and len(t) <= 10: visualize_dp_table(s, t, dp)DP Table Visualization for s="rabbbit", t="rabbit":
ε 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
Notice how the count at dp[6][5] for "rabbbi" → "rabbi" is 3, which correctly counts the three ways to choose 2 b's from 3 b's.
The 2D solution uses O(n × m) space, which can be problematic for long strings. We can optimize to O(m) space by observing the dependency pattern.
Key Observation:
Each cell dp[i][j] depends only on:
dp[i-1][j] (directly above)dp[i-1][j-1] (diagonally above-left)This means we only need the previous row to compute the current row. Better yet, we can use a single 1D array if we iterate right-to-left within each row.
Why Right-to-Left?
If we iterate left-to-right, updating dp[j] would overwrite the value we need for dp[j+1] (since dp[j] would become the new row's value before we use it as the "previous row's dp[j]" for computing dp[j+1]).
By iterating right-to-left, when we compute dp[j], dp[j-1] still holds the previous row's value (which we need as dp[i-1][j-1]), and dp[j] itself holds the previous row's value (which we need as dp[i-1][j]).
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108
def num_distinct_optimized(s: str, t: str) -> int: """ Space-optimized solution using 1D DP array. Time Complexity: O(n * m) Space Complexity: O(m) - only stores one row The key insight is that each row only depends on the previous row, and we iterate right-to-left to avoid overwriting values we still need. """ n, m = len(s), len(t) if m > n: return 0 # 1D DP array: dp[j] = ways to form t[0..j-1] # After processing s[0..i-1], dp[j] holds dp[i][j] dp = [0] * (m + 1) dp[0] = 1 # Base case: empty target for i in range(1, n + 1): # CRITICAL: Iterate right-to-left! # This ensures dp[j-1] still holds the previous row's value for j in range(m, 0, -1): if s[i - 1] == t[j - 1]: # dp[j] <- dp[i-1][j-1] + dp[i-1][j] # dp[j] (current) uses dp[j-1] (prev row) and dp[j] (prev row) dp[j] = dp[j - 1] + dp[j] # If characters don't match, dp[j] = dp[i-1][j] # which is already in dp[j], so no update needed! return dp[m] def num_distinct_with_pruning(s: str, t: str) -> int: """ Further optimized with early termination. If at any point we don't have enough remaining characters in s to possibly complete t, we can stop early. """ n, m = len(s), len(t) if m > n: return 0 dp = [0] * (m + 1) dp[0] = 1 for i in range(1, n + 1): # How many source characters remain after this one? remaining = n - i # Only need to update dp[j] where j <= i (can't form more than i chars) # and where m - j <= remaining (enough chars left to complete) max_j = min(m, i) min_j = max(1, m - remaining) for j in range(max_j, min_j - 1, -1): if s[i - 1] == t[j - 1]: dp[j] = dp[j - 1] + dp[j] return dp[m] def num_distinct_modular(s: str, t: str, mod: int = 10**9 + 7) -> int: """ Version with modular arithmetic to handle very large answers. Some variations of this problem ask for the answer modulo 10^9 + 7. """ n, m = len(s), len(t) if m > n: return 0 dp = [0] * (m + 1) dp[0] = 1 for i in range(1, n + 1): for j in range(m, 0, -1): if s[i - 1] == t[j - 1]: dp[j] = (dp[j - 1] + dp[j]) % mod return dp[m] # Comparison of all approachesif __name__ == "__main__": import time s = "rabbbit" t = "rabbit" print(f"s='{s}', t='{t}'") print(f"Standard 2D: {num_distinct(s, t)}") print(f"Optimized 1D: {num_distinct_optimized(s, t)}") print(f"With pruning: {num_distinct_with_pruning(s, t)}") print(f"Modular: {num_distinct_modular(s, t)}") # Benchmark on larger input s_large = "a" * 1000 t_large = "a" * 100 start = time.time() result = num_distinct_optimized(s_large, t_large) elapsed = time.time() - start print(f"\nLarge input (1000, 100): {result} in {elapsed:.4f}s")The direction of the inner loop is crucial. If you iterate left-to-right, you'll use the newly computed dp[j-1] instead of the previous row's dp[j-1], giving wrong results. This is a common bug in space-optimized DP solutions. Always trace through a small example to verify.
Time Complexity: O(n × m)
Space Complexity:
| Version | Space | Notes |
|---|---|---|
| 2D DP | O(n × m) | Full table |
| 1D DP | O(m) | Single row, reused |
| With pruning | O(m) | Same, slightly fewer ops |
When Does This Blow Up?
The answer can be astronomically large. Consider:
s = "aaaa...a" (n copies of 'a')
t = "aaa...a" (m copies of 'a')
This is equivalent to counting ways to choose m positions from n positions, which is C(n, m) = n! / (m! × (n-m)!)
For n = 1000 and m = 500, this is a number with hundreds of digits! That's why some problem variants require modular arithmetic.
| Approach | Time | Space | Practical Use Case |
|---|---|---|---|
| Brute Force (enumerate subsequences) | O(2^n × m) | O(n) | n ≤ 20 only |
| 2D DP | O(n × m) | O(n × m) | Visualization, debugging |
| 1D DP (optimized) | O(n × m) | O(m) | Production, interviews |
| With pruning + modular | O(n × m) | O(m) | Competition problems |
For interview constraints (n, m ≤ 1000), the O(n × m) solution runs in under 100ms. For competitive programming with larger constraints (n, m ≤ 10^5), you'd need O(n × m) with good constant factors, or problem-specific optimizations.
Distinct Subsequences belongs to a family of sequence counting problems. Understanding the relationships helps recognize patterns in new problems.
Is Subsequence (LeetCode 392):
The simpler version: just determine YES/NO whether t is a subsequence of s. This can be solved in O(n) with two pointers, no DP needed.
Number of Matching Subsequences (LeetCode 792):
Given words array and string s, count how many words are subsequences of s. This requires checking multiple targets efficiently.
Count Different Palindromic Subsequences (LeetCode 730):
Count distinct non-empty palindromic subsequences. Much harder—requires careful state design to avoid overcounting.
Longest Common Subsequence (LeetCode 1143):
Instead of counting, find the length of the longest common subsequence. Related recurrence structure but maximizing instead of counting.
Edit Distance (LeetCode 72):
Minimize operations to transform one string to another. Similar 2D DP structure but with different transitions.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
def is_subsequence(s: str, t: str) -> bool: """ LeetCode 392: Is Subsequence Check if s is a subsequence of t. Two-pointer approach: O(n) time, O(1) space. """ if not s: return True s_ptr = 0 for char in t: if char == s[s_ptr]: s_ptr += 1 if s_ptr == len(s): return True return False def longest_common_subsequence(text1: str, text2: str) -> int: """ LeetCode 1143: Longest Common Subsequence Find length of LCS. Similar structure to distinct subsequences but we maximize instead of count. Time: O(n * m) Space: O(m) with optimization """ n, m = len(text1), len(text2) dp = [0] * (m + 1) for i in range(1, n + 1): prev = 0 # dp[i-1][j-1] for j in range(1, m + 1): temp = dp[j] # Save dp[i-1][j] before overwriting if text1[i - 1] == text2[j - 1]: dp[j] = prev + 1 else: dp[j] = max(dp[j], dp[j - 1]) prev = temp return dp[m] def count_subsequences_equal_to_any(s: str, words: list[str]) -> int: """ Count how many words are subsequences of s. Optimized approach: preprocess s for faster lookups. For each character, store list of indices where it appears. Use binary search to find next occurrence. Time: O(|s| + sum(|word|) * log|s|) """ from collections import defaultdict import bisect # Preprocess: char -> list of indices char_indices = defaultdict(list) for i, char in enumerate(s): char_indices[char].append(i) def is_subsequence_fast(word: str) -> bool: """Check using binary search on precomputed indices.""" current_pos = -1 for char in word: if char not in char_indices: return False indices = char_indices[char] # Find smallest index > current_pos idx = bisect.bisect_right(indices, current_pos) if idx == len(indices): return False current_pos = indices[idx] return True return sum(1 for word in words if is_subsequence_fast(word)) # Testprint(f"is_subsequence('abc', 'ahbgdc') = {is_subsequence('abc', 'ahbgdc')}")print(f"LCS('abcde', 'ace') = {longest_common_subsequence('abcde', 'ace')}")print(f"count_subsequences('abcde', ['a', 'bb', 'acd', 'ace']) = " f"{count_subsequences_equal_to_any('abcde', ['a', 'bb', 'acd', 'ace'])}")Connecting the Recurrences:
| Problem | Recurrence (when match) | Recurrence (no match) | Goal |
|---|---|---|---|
| Distinct Subsequences | dp[i-1][j-1] + dp[i-1][j] | dp[i-1][j] | Count |
| LCS Length | dp[i-1][j-1] + 1 | max(dp[i-1][j], dp[i][j-1]) | Maximize |
| Edit Distance | dp[i-1][j-1] | 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) | Minimize |
Notice how all three problems share the 2D DP structure with character matching at the core. The operations performed (add/max/min) differ based on what we're optimizing.
Distinct Subsequences is a masterclass in sequence DP, demonstrating how to count combinatorial objects using dynamic programming.
You now understand the Distinct Subsequences problem deeply—from the recurrence derivation through space optimization. This is one of the classic DP problems that tests true understanding of dynamic programming principles. Next, we'll explore Edit Distance variations, rounding out our coverage of string algorithm patterns.