Distinct Subsequences
Problem
Given two strings s and t, return the number of distinct subsequences of s which equals t.
- 0 ≤ s.length, t.length ≤ 1000
- s and t consist of English letters.
Example
s = "rabbbit", t = "rabbit"3The string "rabbbit" has 3 distinct subsequences that equal "rabbit". The algorithm explores the string s starting from index 0 and t from index 0. At each step, if characters match, it considers two paths: matching these characters and moving both indices forward, or skipping the current character in s and moving only s's index forward. If characters don't match, it skips the current character in s. Memoization caches results for each (i, j) pair to avoid redundant computations. The critical insight is that the problem breaks down into counting subsequences by exploring these two choices recursively, and memoization ensures polynomial time complexity.
Approach
Straightforward Solution
A brute-force recursive approach tries all subsequences of s and checks if they equal t, resulting in exponential time due to repeated exploration of the same states.
Core Observation
The count of subsequences matching t from position j in s starting at position i depends on whether s[i] matches t[j]. If they match, the total count is the sum of counts from advancing both indices and counts from skipping s[i]. If they don't match, only skipping s[i] is valid. This recursive structure exhibits overlapping subproblems and optimal substructure.
Path to Optimal
Recognizing the overlapping subproblems, memoization is introduced to cache results for each (i, j) state, preventing redundant computations. This transforms the exponential recursion into a polynomial time dynamic programming solution. The problem is thus modeled as a top-down DP with memoization over indices of s and t.
Optimal Approach
Implement a recursive function dp(i, j) that returns the number of subsequences of s[i:] matching t[j:]. Use memoization to cache results. If characters match, sum the counts of matching both characters and skipping s[i]. If not, skip s[i]. Base cases handle when t is fully matched (return 1) or s is exhausted without matching t (return 0). This approach guarantees O(n*m) time and space complexity, where n and m are lengths of s and t respectively.
Time
O(n * m)
Each state (i, j) is computed once and cached. There are at most n * m states, where n = len(s) and m = len(t). Each state computation takes O(1) time.
Space
O(n * m)
The memoization dictionary stores results for each pair of indices (i, j), requiring O(n * m) auxiliary space. The recursion stack depth is at most O(n + m), which is bounded by O(n * m).
Pattern Spotlight
Dynamic Programming (Top-Down Memoization for Counting Subsequences)
When counting subsequences or combinations with overlapping subproblems, model the problem as a state machine over indices and cache results to avoid exponential recomputation, transforming recursion into efficient DP.
Solution
| 1 | class Solution:
|
| 2 | def numDistinct(self, s: str, t: str) -> int:
|
| 3 | memo = {}
|
| 4 |
|
| 5 | def dp(i, j):
|
| 6 | if j == len(t):
|
| 7 | return 1
|
| 8 | if i == len(s):
|
| 9 | return 0
|
| 10 | if (i, j) in memo:
|
| 11 | return memo[(i, j)]
|
| 12 |
|
| 13 | if s[i] == t[j]:
|
| 14 | memo[(i, j)] = dp(i + 1, j + 1) + dp(i + 1, j)
|
| 15 | else:
|
| 16 | memo[(i, j)] = dp(i + 1, j)
|
| 17 |
|
| 18 | return memo[(i, j)]
|
| 19 |
|
| 20 | return dp(0, 0) |
Step-by-Step Solution
Cache Recursive Results to Avoid Redundant Computations
| 3 | memo = {}
|
| 10 | if (i, j) in memo:
|
| 11 | return memo[(i, j)]
|
Objective
To store the results of subproblems defined by indices (i, j) to prevent exponential recomputation.
Key Insight
Memoization transforms the naive recursive solution into an efficient dynamic programming approach by caching the number of subsequences for each pair of indices. This avoids recomputing the same subproblems multiple times, which is the main cause of exponential time complexity in naive recursion.
Interview Quick-Check
Core Logic
Memoization caches results keyed by (i, j), ensuring each subproblem is solved once.
Common Pitfalls & Bugs
Forgetting to cache results leads to exponential time due to repeated exploration of identical states.
Return 1 When Target Fully Matched and 0 When Source Exhausted
| 6 | if j == len(t):
|
| 7 | return 1
|
| 8 | if i == len(s):
|
| 9 | return 0
|
Objective
To define base cases that terminate recursion when the target string is fully matched or the source string is exhausted without a match.
Key Insight
When the target index reaches its length, it means a valid subsequence has been found, so return 1. Conversely, if the source index reaches its length before the target is matched, no subsequence can be formed, so return 0. These base cases anchor the recursion and ensure correctness.
Interview Quick-Check
State & Boundaries
Return 1 when j == len(t) because the entire target has been matched.
State & Boundaries
Return 0 when i == len(s) but j < len(t) because no further matches are possible.
Sum Counts of Matching and Skipping Characters to Count Subsequences
| 13 | if s[i] == t[j]:
|
| 14 | memo[(i, j)] = dp(i + 1, j + 1) + dp(i + 1, j)
|
| 15 | else:
|
| 16 | memo[(i, j)] = dp(i + 1, j)
|
Objective
To compute the number of subsequences by considering both matching the current characters and skipping the current character in s.
Key Insight
If s[i] matches t[j], the total count includes subsequences that use this match (advancing both indices) and subsequences that skip s[i] (advancing only s's index). If characters don't match, only skipping s[i] is valid. This dual-path recursion captures all distinct subsequences without double counting.
Interview Quick-Check
Core Logic
When characters match, add counts from matching both and skipping s[i]; otherwise, only skip s[i].
Common Pitfalls & Bugs
Failing to consider both paths when characters match leads to undercounting subsequences.
Return Cached Result to Complete Recursive Computation
| 18 | return memo[(i, j)]
|
Objective
To return the computed or cached number of subsequences for the current indices.
Key Insight
Returning the memoized result ensures the recursion correctly propagates the count of subsequences up the call stack. This line finalizes the DP step by providing the answer for the current state.
Interview Quick-Check
Core Logic
Return the cached result for (i, j) to avoid recomputation and propagate the count.
Initiate Recursive Counting from Start of Both Strings
| 20 | return dp(0, 0) |
Objective
To start the recursive counting process from the beginning of s and t.
Key Insight
Calling dp(0, 0) begins the exploration of all subsequences of s that could match t, leveraging the memoized recursive structure to efficiently count all valid subsequences.
Interview Quick-Check
Core Logic
Starting at indices 0, 0 ensures the entire strings are considered from the beginning.
Line Analysis
This solution has 8 Critical lines interviewers watch for.
if j == len(t):Check if the target string has been fully matched.
When j equals the length of t, it means a valid subsequence has been found, so return 1 to count this successful path.
if i == len(s):Check if the source string has been exhausted before matching the target.
If i equals the length of s but j is not at the end of t, no further subsequences can match, so return 0 to indicate failure.
memo[(i, j)] = dp(i + 1, j + 1) + dp(i + 1, j)Calculate and cache the sum of counts from matching and skipping the current character.
This line embodies the core DP recurrence: when characters match, the total count is the sum of subsequences that include this match and those that skip it, ensuring all distinct subsequences are counted.
memo = {}Initialize a memoization dictionary to cache results of subproblems.
Memoization is essential to avoid exponential recomputation by storing results for each (i, j) state, enabling efficient top-down dynamic programming.
return 1Return 1 to count a successful subsequence match.
Returning 1 here signals that one valid subsequence has been found, serving as a base case for the recursion.
return 0Return 0 to indicate no valid subsequence can be formed.
This base case prevents invalid paths from contributing to the count, ensuring correctness.
if (i, j) in memo:Check if the current subproblem result is already cached.
This lookup prevents redundant computation by returning the cached result if available, a key optimization for efficiency.
return memo[(i, j)]Return the cached result for the current indices.
Returning the memoized value ensures the recursion uses previously computed results, avoiding exponential time complexity.
if s[i] == t[j]:Check if the current characters in s and t match.
Matching characters enable two recursive paths: using the match or skipping the character in s, which together count all valid subsequences.
else:Handle the case where characters do not match.
If characters differ, only skipping the current character in s is valid, so the count is derived solely from dp(i + 1, j).
memo[(i, j)] = dp(i + 1, j)Cache the count of subsequences when characters do not match.
Caching this result prevents redundant computation for this state, maintaining efficiency.
return memo[(i, j)]Return the cached count of subsequences for the current state.
Returning the memoized result completes the recursive step, propagating the count up the call stack.
return dp(0, 0)Start the recursive counting from the beginning of both strings.
This call initiates the entire DP process, exploring all subsequences of s that could match t.
Test Your Understanding
Why does the algorithm add the results of dp(i + 1, j + 1) and dp(i + 1, j) when s[i] == t[j]?
Because when characters match, the total count includes subsequences that use this matching pair (dp(i + 1, j + 1)) and subsequences that skip the current character in s (dp(i + 1, j)), ensuring all distinct subsequences are counted without omission or duplication.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Distinct Subsequences from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Distinct Subsequences drill