This problem requires counting how many ways string t can appear as a subsequence in string s using a DP table. By defining dp[i][j] as the number of ways t[0..j-1] appears in s[0..i-1], you can build solutions incrementally. Carefully handling character matches and mismatches ensures correct accumulation without overcounting overlapping subsequences.
Problem Statement
Given two strings s and t, calculate the total number of distinct subsequences in s that match t exactly. Each subsequence must maintain the original order of characters from s but can skip any number of characters.
You must return an integer representing the count of these distinct subsequences. The inputs are guaranteed such that the answer fits in a 32-bit signed integer, with s and t consisting only of English letters, and lengths ranging from 1 to 1000.
Examples
Example 1
Input: s = "rabbbit", t = "rabbit"
Output: 3
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
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.
Solution Approach
Dynamic Programming Table Setup
Create a 2D dp array where dp[i][j] represents the number of ways the first j characters of t can be formed from the first i characters of s. Initialize dp[0][0] = 1 and dp[i][0] = 1 for all i, since an empty t is always a subsequence.
State Transition Rules
For each character in s, if it matches the current character in t, dp[i][j] = dp[i-1][j-1] + dp[i-1][j]. If it does not match, inherit the previous count: dp[i][j] = dp[i-1][j]. This ensures all valid subsequences are counted without duplication.
Space Optimization
Since dp[i][j] only depends on the previous row, use a single 1D array to reduce space complexity from O(n*m) to O(m). Update the array in reverse order for t indices to preserve previous values during iteration.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(nm) for strings of lengths n and m, as each dp cell is computed once. Space complexity is O(m) with optimization, otherwise O(nm). Performance depends on careful DP state updates to avoid overcounting.
What Interviewers Usually Probe
- Check if the candidate identifies dp[i][j] meaning and proper initialization.
- Watch if they correctly implement the state transition without skipping edge cases.
- Notice if they attempt space optimization or remain with full 2D table.
Common Pitfalls or Variants
Common pitfalls
- Confusing character positions and misaligning indices in the dp table.
- Forgetting to initialize dp[i][0] = 1, which causes incorrect counts for empty target subsequences.
- Overwriting previous dp values during optimization, leading to undercounting.
Follow-up variants
- Compute subsequences modulo a large prime to prevent integer overflow.
- Count distinct subsequences that match t but allow at most k skipped characters in between.
- Find the minimum-length subsequence in s that can generate t multiple times.
How GhostInterview Helps
- Breaks down dp table creation and state transitions step by step for this exact problem.
- Highlights subtle failure modes like index misalignment and incorrect accumulation during character mismatches.
- Offers optimized strategies to reduce memory usage while maintaining accurate subsequence counting.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What is the main pattern behind the Distinct Subsequences problem?
It follows state transition dynamic programming where dp[i][j] counts ways to form t[0..j-1] from s[0..i-1].
Can this problem be solved without dynamic programming?
Recursive solutions exist but are inefficient due to overlapping subproblems; DP ensures polynomial time.
How do you handle empty target strings?
An empty target t is a subsequence of any prefix of s, so dp[i][0] = 1 for all i.
Is space optimization important here?
Yes, using a 1D array reduces space from O(n*m) to O(m) while preserving correct counts.
What common mistakes should be avoided?
Misaligned indices, forgetting base cases, and overwriting previous dp values during optimization are frequent errors.
Need direct help with Distinct Subsequences instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Distinct Subsequences from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Find all possible palindrome partitioning of a string using backtracking and dynamic programming.
Open problem page#132 Palindrome Partitioning IIDetermine the minimum cuts required to partition a string into all palindromic substrings using dynamic programming techniques.
Open problem page#97 Interleaving StringThe Interleaving String problem requires determining if a string can be formed by interleaving two others, utilizing dynamic programming techniques.
Open problem page