Distinct Subsequences - Solution & Explanation
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.rabbbitrabbbitrabbbit
Example 2:
Input: s = "babgbag", t = "bag" Output: 5 Explanation: As shown below, there are 5 ways you can generate "bag" from s.babgbagbabgbagbabgbagbabgbagbabgbag
Constraints:
1 <= s.length, t.length <= 1000sandtconsist of English letters.
Approach Overview
Problem Overview: Given two strings s and t, count how many distinct subsequences of s equal t. A subsequence keeps character order but can skip characters. The challenge is avoiding exponential exploration while counting all valid combinations.
Approach 1: Dynamic Programming 2D Table (O(m * n) time, O(m * n) space)
This approach builds a 2D DP table where dp[i][j] represents the number of ways the first i characters of s can form the first j characters of t. Initialize dp[i][0] = 1 because an empty string t can always be formed by deleting characters from s. Then iterate through both strings. If s[i-1] == t[j-1], add two possibilities: use the character (dp[i-1][j-1]) or skip it (dp[i-1][j]). If they differ, only skip the character in s (dp[i-1][j]). This method explicitly models all prefix combinations, making it easy to reason about and debug. Time complexity is O(m * n) and space complexity is also O(m * n).
This is a classic example of dynamic programming applied to a string matching problem where overlapping subproblems appear when multiple subsequences reuse the same prefixes.
Approach 2: Dynamic Programming with Space Optimization (O(m * n) time, O(n) space)
The full DP table stores many intermediate states that are only used once. Each row depends only on the previous row, so you can compress the table into a single 1D array. Maintain dp[j] as the number of ways to build the first j characters of t. Iterate through s, and update dp from right to left so previous states are not overwritten too early. When s[i-1] == t[j-1], update dp[j] += dp[j-1]. Right-to-left iteration preserves the values from the previous iteration of s. This reduces memory usage significantly while keeping the same O(m * n) runtime.
This optimization matters when the input strings are large, since the DP table can otherwise consume substantial memory. The algorithmic idea remains identical—count subsequence combinations using prefix relationships—but the storage is compressed to a single dimension.
Recommended for interviews: Interviewers usually expect the dynamic programming formulation first because it demonstrates understanding of subsequence counting and state transitions. Start by explaining the 2D DP definition (dp[i][j] meaning prefixes of s and t). Once the recurrence is clear, mention the 1D optimization to reduce space from O(m * n) to O(n). Showing both versions proves you understand both correctness and practical optimization.
Approach 1: Dynamic Programming 2D Table
We use a 2D DP table where `dp[i][j]` represents the number of distinct subsequences of `s[0..i-1]` which forms `t[0..j-1]`. The size of the table is `(m+1)x(n+1)` where `m` is the length of `s` and `n` is the length of `t`.
Initialize `dp[0][0]` to 1 because an empty string is a subsequence of itself, and `dp[i][0]` to 1 for all `i`, because an empty `t` is a subsequence of any prefix of `s`. Then, for each character `s[i-1]` and `t[j-1]`, update the DP table as follows:
- If `s[i-1] == t[j-1]`, then `dp[i][j] = dp[i-1][j-1] + dp[i-1][j]`.
- If `s[i-1] != t[j-1]`, then `dp[i][j] = dp[i-1][j]`.
This C code uses a two-dimensional array `dp` where dp[i][j] contains the number of ways the first `i` characters of `s` can form the first `j` characters of `t`. We initialize the first column (except `dp[0][0]`) to 1 because the empty string `t` is a subsequence of any string `s`. We fill the DP table according to the conditions based on whether the current characters of `s` and `t` match or not, then return the value at dp[m][n], which contains the number of distinct subsequences.
Complexity
Time Complexity: O(m * n), where `m` is the length of `s` and `n` is the length of `t`.
Space Complexity: O(m * n) for the DP table.
Approach 2: Dynamic Programming with Space Optimization
We can optimize the space complexity by observing that to calculate `dp[i][j]`, we only need values from the previous row. Thus, we can use a 2-row approach, maintaining only `previous` and `current` arrays to save space. This reduces the space complexity to O(n), where `n` is the length of `t`.
The transition is similar to the 2D approach but only updates the necessary parts of the `current` array based on the `previous` row.
This C function reduces space usage by utilizing two arrays, alternating between them to store the current and previous results. The modulo operation helps alternate between using `previous` and `current`, simplifying the 2D structure to two 1D arrays.
Complexity
Time Complexity: O(m * n), where `m` is the length of `s` and `n` is the length of `t`.
Space Complexity: O(n), using only two rows for DP storage.
Approach 3: Dynamic Programming
We define f[i][j] as the number of schemes where the first i characters of string s form the first j characters of string t. Initially, f[i][0]=1 for all i \in [0,m].
When i > 0, we consider the calculation of f[i][j]:
- When
s[i-1] \ne t[j-1], we cannot selects[i-1], sof[i][j]=f[i-1][j]; - Otherwise, we can select
s[i-1], sof[i][j]=f[i-1][j-1].
Therefore, we have the following state transition equation:
$
f[i][j]=\left{
\begin{aligned}
&f[i-1][j], &s[i-1] \ne t[j-1] \
&f[i-1][j-1]+f[i-1][j], &s[i-1]=t[j-1]
\end{aligned}
\right.
The final answer is f[m][n], where m and n are the lengths of strings s and t respectively.
The time complexity is O(m times n), and the space complexity is O(m times n).
We notice that the calculation of f[i][j] is only related to f[i-1][..]. Therefore, we can optimize the first dimension, reducing the space complexity to O(n)$.
Approach 4: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming 2D Table | Time Complexity: O(m * n), where `m` is the length of `s` and `n` is the length of `t`. |
| Dynamic Programming with Space Optimization | Time Complexity: O(m * n), where `m` is the length of `s` and `n` is the length of `t`. |
| Dynamic Programming | — |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming 2D Table | O(m * n) | O(m * n) | Best for understanding the recurrence and debugging state transitions |
| DP with Space Optimization (1D) | O(m * n) | O(n) | Preferred in interviews and large inputs where memory efficiency matters |
Video Solution
DP 32. Distinct Subsequences | 1D Array Optimisation Technique 🔥 • take U forward • 316,493 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Distinct Subsequences easy or hard?
Distinct Subsequences Python/Java solution
How to solve Distinct Subsequences in O(n)?
What is the best approach for Distinct Subsequences?
Is Distinct Subsequences asked at Google/Amazon/Meta?
What data structure is used in Distinct Subsequences?
What is the time complexity of Distinct Subsequences?
Ready to solve this problem?
Practice Distinct Subsequences with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor