Log inSign up
hardLeetCodeNot Started

Distinct Subsequences

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

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 64-bit signed integer (or 32-bit unsigned integer).

A string's subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters' relative positions (i.e., "ACE" is a subsequence of "ABCDE" while "AEC" is not).

### Example 1 - Input: s = "rabbbit", t = "rabbit" - Output: 3 - Explanation: There are 3 ways you can generate "rabbit" from "rabbbit": - rabbbit (delete 3rd b) - rabbbit (delete 2nd b) - rabbbit (delete 1st b)

### Example 2 - Input: s = "babgbag", t = "bag" - Output: 5 - Explanation: There are 5 ways to generate "bag" from "babgbag".

Constraints:

  • 1 <= s.length, t.length <= 1000
  • s and t consist of English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Distinguish between optimization DP (LCS max length) and counting DP (Distinct Subsequences total count).
  • Derive the 2D matching recurrence relation.
  • Optimize memory to O(|t|) by iterating backwards.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Counting subsequences of one string matching another string.
  • Two-string matrix with skip vs match choices.

Algorithmic Decision Tree:

  • If characters match -> sum of taking the match and skipping.
  • If characters differ -> strictly inherit from skipping s[i-1].

Connected Patterns:

Longest Common SubsequenceEdit DistanceInterleaving String

1. Recursive Suffix Matching

Intuition

At each index pair (i, j), if s[i] == t[j], branch into matching and skipping; otherwise skip s[i].

Algorithm

  1. Define dfs(i, j).
  2. If j == t.length, return 1 (matched entire string t).
  3. If i == s.length, return 0 (s exhausted before matching t).
  4. If s[i] == t[j]: return dfs(i + 1, j + 1) + dfs(i + 1, j).
  5. Else: return dfs(i + 1, j).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3
4using namespace std;
5
6int dfs(int i, int j, const string& s, const string& t) {
7 if (j == (int)t.length()) return 1;
8 if (i == (int)s.length()) return 0;
9
10 if (s[i] == t[j]) {
11 return dfs(i + 1, j + 1, s, t) + dfs(i + 1, j, s, t);
12 } else {
13 return dfs(i + 1, j, s, t);
14 }
15}
16
17int numDistinctRec(string s, string t) {
18 return dfs(0, 0, s, t);
19}
20
21int main() {
22 string s = "rabbbit", t = "rabbit";
23 cout << "Distinct Subsequences (Recursive): " << numDistinctRec(s, t) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(2^|s|)
  • Space complexity: O(|s|) call stack

2. 2D Dynamic Programming Tabulation

Intuition

Build table dp[m + 1][n + 1] where dp[i][j] is the number of distinct subsequences of s[0..i-1] matching t[0..j-1].

Algorithm

  1. Let m = s.length, n = t.length.
  2. Create dp[m + 1][n + 1] filled with 0 (use unsigned long long in C++ to prevent overflow).
  3. For i = 0 to m: dp[i][0] = 1.
  4. For i = 1 to m:
  5. For j = 1 to n:
  6. If s[i - 1] == t[j - 1]:
  7. dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
  8. Else: dp[i][j] = dp[i - 1][j]
  9. Return dp[m][n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7int numDistinct2D(string s, string t) {
8 int m = s.length(), n = t.length();
9 vector<vector<unsigned long long>> dp(m + 1, vector<unsigned long long>(n + 1, 0));
10
11 for (int i = 0; i <= m; i++) dp[i][0] = 1;
12
13 for (int i = 1; i <= m; i++) {
14 for (int j = 1; j <= n; j++) {
15 if (s[i - 1] == t[j - 1]) {
16 dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
17 } else {
18 dp[i][j] = dp[i - 1][j];
19 }
20 }
21 }
22 return dp[m][n];
23}
24
25int main() {
26 string s = "rabbbit", t = "rabbit";
27 cout << "Distinct Subsequences (2D DP): " << numDistinct2D(s, t) << endl;
28 return 0;
29}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

3. 1D Array Space-Optimized Tabulation

Intuition

Maintain a single array dp of size |t| + 1. Traverse j in reverse order from |t| down to 1.

Algorithm

  1. Let n = t.length.
  2. Create array dp of size n + 1 filled with 0.
  3. dp[0] = 1.
  4. For each char c in s:
  5. For j = n down to 1:
  6. If c == t[j - 1]:
  7. dp[j] += dp[j - 1].
  8. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7int numDistinctOptimal(string s, string t) {
8 int n = t.length();
9 vector<unsigned long long> dp(n + 1, 0);
10 dp[0] = 1;
11
12 for (char c : s) {
13 for (int j = n; j >= 1; j--) {
14 if (c == t[j - 1]) {
15 dp[j] += dp[j - 1];
16 }
17 }
18 }
19 return dp[n];
20}
21
22int main() {
23 string s = "rabbbit", t = "rabbit";
24 cout << "Distinct Subsequences (Optimal 1D DP): " << numDistinctOptimal(s, t) << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(|s| * |t|)
  • Space complexity: O(|t|) space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Suffix MatchingO(2^|s|)O(|s|)Exhaustive branching over matching vs skipping.Redundant states
2.2D TabulationO(|s| * |t|)O(|s| * |t|)2D table storing prefix subsequence match counts.Matrix allocation
3.1D Backward TabulationOptimalO(|s| * |t|)O(|t|)Single 1D array traversed in reverse.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Integer overflow during intermediate additions (always use 64-bit unsigned integers in C++ or BigInt in JS).

Pitfall 2:

Iterating forward in the 1D array.

Crucial Edge Cases to Validate:

  • |s| < |t|: Output is 0 (s cannot contain a longer subsequence).
  • s equals t: Output is 1.
  • t is empty: Output is 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Contrast this problem with Longest Common Subsequence (LCS): LCS takes max(skip_s, skip_t), whereas Distinct Subsequences takes sum(match, skip_s) because we are counting distinct valid ways.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the inner loop over string t run backwards (from |t| down to 1) when using a 1D DP array?

Back to DSA Sheet