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 <= 1000s and t consist of English letters.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.
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:
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.
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.
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.
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.
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]:
s[i-1] \ne t[j-1], we cannot select s[i-1], so f[i][j]=f[i-1][j];s[i-1], so f[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)$.
Python
Java
C++
Go
TypeScript
| 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 | — |
| 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 |
DP 32. Distinct Subsequences | 1D Array Optimisation Technique 🔥 • take U forward • 291,445 views views
Watch 9 more video solutions →Practice Distinct Subsequences with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor