Skip to main content
CodePeetCodePeet
CodePeet 150

Distinct Subsequences

HARDProblemSolveExternal Links

Description

Given two strings s and t, return the number of distinct subsequences of s that equal t.

A subsequence of a string is a new string formed by deleting zero or more characters from the original string without changing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde", while "aec" is not.

The answer is guaranteed to fit in a 32-bit signed integer.

Examples

Example 1

Input: s = "rabbbit", t = "rabbit"

Output: 3

Explanation: There are three distinct ways to select characters from s to form t = "rabbit":

  • Choose the 1st, 2nd, 3rd 'b': rabbbit
  • Choose the 1st, 2nd, 3rd 'b': rabbbit
  • Choose 1st, 2nd, 3rd 'b': rabbbit

Each selection deletes a different 'b', yielding three distinct subsequences.

Example 2

Input: s = "babgbag", t = "bag"

Output: 5

Explanation: There are five distinct ways to select characters from "babgbag" to form "bag":

  • babgbag (positions 0,1,3)
  • babgbag (positions 0,1,6)
  • babgbag (positions 0,5,6)
  • babgbag (positions 2,5,6)
  • babgbag (positions 4,5,6)

Example 3

Input: s = "aab", t = "ab"

Output: 2

Explanation: We can pick the first 'a' paired with 'b' (positions 0,2), or the second 'a' paired with 'b' (positions 1,2). Two distinct subsequences form "ab".

Constraints

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

Editorial

Brute Force - Pure Recursion

Intuition

The most natural way to think about this problem is with a choice at every position in s: for each character, should we use it to match the current character of t, or should we skip it?

Imagine you are reading a book (string s) and you need to highlight characters to spell out a target word (string t). You go character by character through the book. When the current book character matches the current target character, you have two options: highlight it (matching it to t) and move to the next target character, or skip it and keep looking for another copy later. When the characters don't match, you have no choice — just skip and move on.

This recursive process explores all possible ways to form t from s. Each complete path from the start to matching all of t counts as one valid subsequence.

Step-by-Step Explanation

Let's trace through Example 2: s = "babgbag", t = "bag"

We define f(i, j) as the number of ways to form t[j..] from s[i..]. Our answer is f(0, 0).

Step 1: Call f(0, 0). s[0]='b', t[0]='b'. Match! Branch into:

  • f(1, 1): use s[0] to match t[0], move both forward
  • f(1, 0): skip s[0], keep looking for 'b'

Step 2: Follow f(1, 1). s[1]='a', t[1]='a'. Match! Branch into f(2, 2) and f(2, 1).

Step 3: Follow f(2, 2). s[2]='b', t[2]='g'. No match. Only option: f(3, 2).

Step 4: Follow f(3, 2). s[3]='g', t[2]='g'. Match! Branch into f(4, 3) and f(4, 2).

Step 5: f(4, 3): j=3=len(t). All characters of t are matched! Found one valid subsequence. Return 1.

Step 6: Follow f(4, 2): s[4]='b'≠t[2]='g', skip → f(5, 2). s[5]='a'≠'g', skip → f(6, 2).

Step 7: f(6, 2): s[6]='g'==t[2]='g'. Match! Branch into f(7, 3) and f(7, 2).

Step 8: f(7, 3): j=3=len(t). Another valid subsequence! Return 1.

Step 9: f(7, 2): i=7=len(s). Exhausted s without matching all of t. Return 0.

Step 10: Results bubble up: f(6,2)=1, f(5,2)=1, f(4,2)=1, f(3,2)=1+1=2, f(2,2)=2.

Step 11: Now explore f(2, 1) branch — where we skipped the first 'a'. This branch and the f(1, 0) branch together find the remaining 3 subsequences.

Step 12: The full recursion completes with f(0, 0) = 5. But states like f(6, 2) are reached through multiple branches and recomputed each time — exponential redundancy.

Recursive Exploration — Branching on Match/Skip Choices — Watch how each character match in s creates two branches (use it or skip it), while mismatches force a single skip path. The tree grows exponentially.

Algorithm

  1. Define recursive function f(i, j) = number of ways to form t[j..end] from s[i..end]
  2. Base cases:
    • If j == len(t): all of t is matched → return 1
    • If i == len(s): s is exhausted before matching all of t → return 0
  3. Recursive case:
    • Always try skipping s[i]: result = f(i+1, j)
    • If s[i] == t[j], also try using s[i] to match t[j]: result += f(i+1, j+1)
  4. Return f(0, 0)

Code

class Solution {
public:
    int numDistinct(string s, string t) {
        return solve(s, t, 0, 0);
    }

private:
    int solve(string& s, string& t, int i, int j) {
        if (j == (int)t.size()) return 1;
        if (i == (int)s.size()) return 0;

        int result = solve(s, t, i + 1, j);
        if (s[i] == t[j]) {
            result += solve(s, t, i + 1, j + 1);
        }
        return result;
    }
};
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        def solve(i: int, j: int) -> int:
            if j == len(t):
                return 1
            if i == len(s):
                return 0

            result = solve(i + 1, j)
            if s[i] == t[j]:
                result += solve(i + 1, j + 1)
            return result

        return solve(0, 0)
class Solution {
    public int numDistinct(String s, String t) {
        return solve(s, t, 0, 0);
    }

    private int solve(String s, String t, int i, int j) {
        if (j == t.length()) return 1;
        if (i == s.length()) return 0;

        int result = solve(s, t, i + 1, j);
        if (s.charAt(i) == t.charAt(j)) {
            result += solve(s, t, i + 1, j + 1);
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(2^m) where m = len(s)

In the worst case (when every character of s matches the current character of t), each position in s creates two branches. This exponential branching can generate up to 2^m recursive calls. With m up to 1000, this is completely infeasible.

Space Complexity: O(m)

The recursion stack depth is at most m (the length of s), since each recursive call advances i by 1.

Why This Approach Is Not Efficient

The pure recursion has exponential time complexity O(2^m). With s up to length 1000, this means up to 2^1000 operations — astronomically beyond any time limit.

The root cause is overlapping subproblems: the same state f(i, j) is recomputed many times through different recursion paths. For example, f(6, 2) can be reached via multiple routes — by using different earlier characters of s — but the answer is always the same regardless of how we got there.

There are only m × n = len(s) × len(t) unique states (i, j). If we store the result of each state the first time it's computed and reuse it thereafter, we avoid all redundant work. This is exactly what dynamic programming provides — either through top-down memoization or bottom-up tabulation — reducing the time from O(2^m) to O(m × n).

Better Approach - 2D Dynamic Programming

Intuition

Instead of recursing from the top down and risking redundant computations, we can build the solution from the bottom up using a 2D table.

Define dp[i][j] as the number of distinct subsequences of s[0..i-1] that equal t[0..j-1]. We fill the table row by row, where each row corresponds to adding one more character from s.

The key insight for the transition is:

  • If s[i-1] == t[j-1] (characters match): we have two options — use this character to match (which gives dp[i-1][j-1] ways) or skip it (which gives dp[i-1][j] ways). Total: dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
  • If s[i-1] != t[j-1] (characters differ): we must skip s[i-1], so dp[i][j] = dp[i-1][j]

This is like building a table where each cell asks: "How many ways can I form the first j characters of t using the first i characters of s?" Each new character from s either adds new possibilities (when it matches) or maintains the existing count (when it doesn't).

Step-by-Step Explanation

Let's trace with s = "babgbag", t = "bag". The table has 8 rows (for ""+s) and 4 columns (for ""+t).

Step 1: Fill base cases. dp[i][0] = 1 for all i (empty t is always a subsequence). dp[0][j] = 0 for j > 0 (can't form non-empty t from empty s).

Step 2: Row 1 (s[0]='b'): dp[1][1]: 'b'=='b' (match!) → dp[0][0] + dp[0][1] = 1 + 0 = 1. One way to match "b" using just s[0].

Step 3: Row 1 continued: dp[1][2]=0, dp[1][3]=0 (no match for 'a' or 'g').

Step 4: Row 2 (s[1]='a'): dp[2][2]: 'a'=='a' (match!) → dp[1][1] + dp[1][2] = 1 + 0 = 1. One way to match "ba" using s[0..1].

Step 5: Row 2: dp[2][1]=1 (copy dp[1][1], 'a'≠'b'). dp[2][3]=0.

Step 6: Row 3 (s[2]='b'): dp[3][1]: 'b'=='b' (match!) → dp[2][0] + dp[2][1] = 1 + 1 = 2. Two 'b's in s[0..2], two ways to match "b".

Step 7: Row 4 (s[3]='g'): dp[4][3]: 'g'=='g' (match!) → dp[3][2] + dp[3][3] = 1 + 0 = 1. First complete "bag" subsequence.

Step 8: Row 5 (s[4]='b'): dp[5][1]: 'b'=='b' → dp[4][0] + dp[4][1] = 1 + 2 = 3. Three 'b' options.

Step 9: Row 6 (s[5]='a'): dp[6][2]: 'a'=='a' → dp[5][1] + dp[5][2] = 3 + 1 = 4. Big jump — 3 ways to start with 'b' combine with 'a'.

Step 10: Row 7 (s[6]='g'): dp[7][3]: 'g'=='g' → dp[6][2] + dp[6][3] = 4 + 1 = 5. Final answer!

Step 11: dp[7][3] = 5. There are 5 distinct subsequences.

2D DP Table — Counting Subsequences Bottom-Up — Watch the table fill row by row. Each match cell combines 'use this character' and 'skip this character' counts. The answer accumulates in the bottom-right corner.

Algorithm

  1. Create a 2D table dp of size (m+1) × (n+1) initialized to 0, where m = len(s), n = len(t)
  2. Base cases: Set dp[i][0] = 1 for all i (empty t is always a subsequence)
  3. Fill table row by row (i from 1 to m):
    • For each j from 1 to n:
      • dp[i][j] = dp[i-1][j] (skip s[i-1])
      • If s[i-1] == t[j-1]: dp[i][j] += dp[i-1][j-1] (use s[i-1] to match t[j-1])
  4. Return dp[m][n]

Code

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<vector<unsigned long long>> dp(m + 1, vector<unsigned long long>(n + 1, 0));

        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j];
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }

        return (int)dp[m][n];
    }
};
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(m + 1):
            dp[i][0] = 1

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                dp[i][j] = dp[i - 1][j]
                if s[i - 1] == t[j - 1]:
                    dp[i][j] += dp[i - 1][j - 1]

        return dp[m][n]
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        long[][] dp = new long[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j];
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }

        return (int) dp[m][n];
    }
}

Complexity Analysis

Time Complexity: O(m × n)

We fill a table with (m+1) rows and (n+1) columns. Each cell requires O(1) work — a comparison and at most two additions. Total: O(m × n) operations.

Space Complexity: O(m × n)

The 2D DP table requires (m+1) × (n+1) cells. With m and n up to 1000, this is up to ~10^6 entries, which is manageable but uses significant memory.

Why This Approach Is Not Efficient

The 2D DP approach has optimal time complexity O(m × n), but its space usage of O(m × n) can be improved.

With m and n both up to 1000, the table requires up to 10^6 entries. While this fits in memory for these constraints, the observation that each row only depends on the previous row means we are storing far more data than needed.

When computing dp[i][j], we only reference dp[i-1][j] and dp[i-1][j-1] — both from the immediately preceding row. All earlier rows are no longer needed. This means we can replace the entire 2D table with a single 1D array of size (n+1), reducing space from O(m × n) to O(n). The key trick is iterating j from right to left to avoid overwriting values that are still needed for the current row's computation.

Optimal Approach - Space-Optimized 1D DP

Intuition

We keep a single 1D array dp of size (n+1) where dp[j] represents the number of ways to form t[0..j-1] using the characters of s we have processed so far.

For each character s[i-1], we update the array. The crucial detail is the update direction: we iterate j from right to left (from n down to 1). This ensures that when we compute dp[j] using dp[j-1], the value dp[j-1] still holds the result from the previous iteration (not yet overwritten by the current one).

Think of it like updating a row of a spreadsheet where each cell depends on the cell to its left from the previous version. If you update left-to-right, you'd overwrite the left cell before the right cell can use its old value. Updating right-to-left avoids this conflict.

When s[i-1] == t[j-1], we add dp[j-1] to dp[j] (the "use this character" option). When they don't match, dp[j] stays the same (the "skip" option — already represented by the current value).

Step-by-Step Explanation

Let's trace with s = "babgbag", t = "bag". dp = [1, 0, 0, 0] initially (dp[0]=1, rest 0).

Step 1: Process s[0]='b'. Scan j from 3 down to 1:

  • j=3: 'b'≠'g', skip. j=2: 'b'≠'a', skip. j=1: 'b'=='b'! dp[1] += dp[0] = 0+1 = 1.
  • dp = [1, 1, 0, 0]

Step 2: Process s[1]='a'. Scan j from 3 down to 1:

  • j=3: 'a'≠'g', skip. j=2: 'a'=='a'! dp[2] += dp[1] = 0+1 = 1. j=1: 'a'≠'b', skip.
  • dp = [1, 1, 1, 0]

Step 3: Process s[2]='b'. j=1: 'b'=='b'! dp[1] += dp[0] = 1+1 = 2.

  • dp = [1, 2, 1, 0]

Step 4: Process s[3]='g'. j=3: 'g'=='g'! dp[3] += dp[2] = 0+1 = 1.

  • dp = [1, 2, 1, 1]

Step 5: Process s[4]='b'. j=1: 'b'=='b'! dp[1] += dp[0] = 2+1 = 3.

  • dp = [1, 3, 1, 1]

Step 6: Process s[5]='a'. j=2: 'a'=='a'! dp[2] += dp[1] = 1+3 = 4.

  • dp = [1, 3, 4, 1]

Step 7: Process s[6]='g'. j=3: 'g'=='g'! dp[3] += dp[2] = 1+4 = 5.

  • dp = [1, 3, 4, 5]

Step 8: dp[3] = 5. Answer: 5.

Space-Optimized 1D DP — In-Place Right-to-Left Updates — Watch how a single 1D array accumulates subsequence counts as we process each character of s. Only matching positions get updated, and the right-to-left scan preserves needed values.

Algorithm

  1. Create a 1D array dp of size (n+1) initialized to 0, where n = len(t)
  2. Set dp[0] = 1 (empty t is always a subsequence)
  3. For each character s[i-1] in s (i from 1 to m):
    • For j from n down to 1 (right-to-left to preserve previous row's values):
      • If s[i-1] == t[j-1]: dp[j] += dp[j-1]
  4. Return dp[n]

Code

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size(), n = t.size();
        vector<unsigned long long> dp(n + 1, 0);
        dp[0] = 1;

        for (int i = 1; i <= m; i++) {
            for (int j = n; j >= 1; j--) {
                if (s[i - 1] == t[j - 1]) {
                    dp[j] += dp[j - 1];
                }
            }
        }

        return (int)dp[n];
    }
};
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [0] * (n + 1)
        dp[0] = 1

        for i in range(1, m + 1):
            for j in range(n, 0, -1):
                if s[i - 1] == t[j - 1]:
                    dp[j] += dp[j - 1]

        return dp[n]
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        long[] dp = new long[n + 1];
        dp[0] = 1;

        for (int i = 1; i <= m; i++) {
            for (int j = n; j >= 1; j--) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[j] += dp[j - 1];
                }
            }
        }

        return (int) dp[n];
    }
}

Complexity Analysis

Time Complexity: O(m × n)

The outer loop runs m times (once per character in s), and the inner loop runs n times (once per character in t). Each iteration does O(1) work. Total: O(m × n), same as the 2D approach.

Space Complexity: O(n)

We use a single 1D array of size (n+1). This is a significant improvement over the O(m × n) space of the 2D table approach. With n up to 1000, we use at most ~1000 entries instead of ~10^6.