Distinct Subsequences

Distinct Subsequences is a counting problem with a twist. You are not matching one string to another. You are counting how many ways one string hides inside another. The interviewer wants to see if you can build a clean two-dimensional table that counts those ways without listing them. That counting skill is the real test here.

🎯 The Problem

You get two strings, s and t. Count how many distinct subsequences of s are exactly equal to t.

The rules:

• A subsequence of s is what is left after you delete some letters from s.
• Deleting must keep the rest of the letters in order.
• You only choose which letters of s to keep. You never reorder them.
• Count the distinct ways to match t inside s.

For s = "rabbbit" and t = "rabbit", the string s has three b letters in a row. To form t you keep one of those b letters and drop the others. There are three ways to choose which b to keep. So the answer is 3.

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

Explanation: pick r a b b i t from "rabbbit" in three ways.
Keep two of the three b's, in these column choices:
  rabb_it   (drop the 3rd b)
  rab_bit   (drop the 2nd b)
  ra_bbit   (drop the 1st b)

Here is the core choice at each letter of s. If the current letter of s matches the current letter of t, you may use it or skip it. If it does not match, you must skip it.

🐢 Approach 1: Try Every Choice (Brute Force)

The idea in one line: walk two pointers and add the counts from skip and use at every match.

The idea:

• Pointer i is the position in s. Pointer j is the position in t.
• At each step, look at s[i] and t[j].

How it works:

• On a match, use the letter and move both pointers, or skip it and move only i. Add both counts.
• On a mismatch, you must skip the letter of s and move only i.
• If j reaches the end of t, that is one full match, so count one.
• If i reaches the end of s but t is not done, count zero.

Why it is weak:

• Each matching letter can split into two paths.
• The number of paths grows close to 2 to the power of the length of s.
• Far too slow for long strings.

Here is the plain recursion code:

def num_distinct(s, t):
    def dfs(i, j):
        if j == len(t):
            return 1
        if i == len(s):
            return 0
        count = dfs(i + 1, j)
        if s[i] == t[j]:
            count += dfs(i + 1, j + 1)
        return count

    return dfs(0, 0)

🧠 Approach 2: Memoization (Better)

The idea in one line: cache the count for each (i, j) pair so paths share work.

The idea:

• The same (i, j) pair gets reached by many paths.
• But the count from a given (i, j) never changes.

How it works:

• Store the count for each (i, j) pair the first time you compute it.
• Next time you reach the same pair, read the saved count.

Why it is fast:

• There are only about len(s) * len(t) pairs.
• The work is bounded by the size of that grid, not the number of paths. This is memoization.

Here is the memoized recursion:

from functools import lru_cache


def num_distinct(s, t):
    @lru_cache(None)
    def dfs(i, j):
        if j == len(t):
            return 1
        if i == len(s):
            return 0
        return dfs(i + 1, j) + (dfs(i + 1, j + 1) if s[i] == t[j] else 0)

    return dfs(0, 0)

🚀 Approach 3: 2D Counting Table (Best)

The idea in one line: fill a grid directly where each cell counts the ways for two prefixes.

The idea:

• Make a table dp where dp[i][j] is the ways the first i letters of s form the first j letters of t.
• Set the first column to one. There is exactly one way to form an empty t: delete every letter of s.
• The rest of the first row is zero. A non-empty t cannot be formed from an empty s.

How it works:

• You can always skip the current letter of s, which gives dp[i-1][j].
• If the current letters match, that is s[i-1] == t[j-1], you may also use the letter, which adds dp[i-1][j-1]. So:

if s[i-1] == t[j-1]:  dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
else:                 dp[i][j] = dp[i-1][j]

Why it is best:

• Each cell is filled once, so the time is O(n times m).
• No recursion and no call stack.
• The answer sits in dp[len(s)][len(t)], which counts all the ways all of s can form all of t.

Steps to Solve

1. Make a dp table of size (len(s)+1) by (len(t)+1), all zeros.
2. Set dp[i][0] = 1 for every i. One way to form an empty t is to delete everything.
3. For each cell, start with dp[i-1][j], which means skip the current letter of s.
4. If s[i-1] equals t[j-1], also add dp[i-1][j-1], which means use the current letter.
5. Return the bottom-right cell dp[len(s)][len(t)].

#include <stdio.h>
#include <string.h>

unsigned long long numDistinct(const char *s, const char *t) {
    int n = strlen(s), m = strlen(t);
    static unsigned long long dp[201][201];

    for (int i = 0; i <= n; i++) dp[i][0] = 1;   // empty t: delete all of s
    for (int j = 1; j <= m; j++) dp[0][j] = 0;   // empty s cannot form t

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            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];     // also use s[i-1]
        }
    }
    return dp[n][m];
}

int main(void) {
    printf("%llu\n", numDistinct("rabbbit", "rabbit"));
    return 0;
}

3

#include <iostream>
#include <vector>
#include <string>
using namespace std;

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

    for (int i = 0; i <= n; i++) dp[i][0] = 1;   // empty t: delete all of s

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            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];     // also use s[i-1]
        }
    }
    return dp[n][m];
}

int main() {
    cout << numDistinct("rabbbit", "rabbit") << endl;
    return 0;
}

3

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

        for (int i = 0; i <= n; i++) dp[i][0] = 1;   // empty t: delete all of s

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

    public static void main(String[] args) {
        System.out.println(numDistinct("rabbbit", "rabbit"));
    }
}

3

def num_distinct(s, t):
    n, m = len(s), len(t)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = 1               # one way to form empty t: delete all of s

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            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]    # also use s[i-1]

    return dp[n][m]


print(num_distinct("rabbbit", "rabbit"))

3

function numDistinct(s, t) {
  const n = s.length, m = t.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(m + 1).fill(0));

  for (let i = 0; i <= n; i++) dp[i][0] = 1;   // empty t: delete all of s

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= m; j++) {
      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];           // also use s[i-1]
      }
    }
  }
  return dp[n][m];
}

console.log(numDistinct("rabbbit", "rabbit"));

3

Let us walk through the Python version line by line. The counting rule is the key.

n, m = len(s), len(t)
dp = [[0] * (m + 1) for _ in range(n + 1)]

We read both lengths. Then we build a grid with one extra row and one extra column. The extra slots stand for empty prefixes. Here dp[i][j] will count the ways the first i letters of s form the first j letters of t.

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

This sets the whole first column to one. An empty t can always be formed in exactly one way. Delete every letter of s. So no matter how much of s we look at, there is one way to match nothing.

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

We fill the rest cell by cell. We always start with dp[i-1][j]. This is the count where we skip the current letter of s. We pretend that letter is not there and reuse the answer without it.

        if s[i - 1] == t[j - 1]:
            dp[i][j] += dp[i - 1][j - 1]

If the current letters match, we have a second option. We can use this letter of s to cover this letter of t. That count comes from dp[i-1][j-1], the answer before both letters. We add it to the skip count. So a matching letter gives both choices summed together.

return dp[n][m]

The bottom-right cell holds the full answer. It counts every distinct way all of s can form all of t.

Here is the filled grid for s = "rabbbit" and t = "rabbit". The three b letters cause the count to grow to three. The bottom-right cell is the answer.

⏱️ Time and Space Complexity

Recursion can split at each matching letter, so it is O(2^n) time. Memoization and the 2D table both visit each (i, j) cell once. There are (n+1) * (m+1) cells. So both are O(n * m) time. The table uses O(n * m) space, but you can shrink it to one row if you reuse it carefully. Here n is the length of s and m is the length of t.

🧩 Key Takeaways

• ✅ dp[i][j] counts the ways the first i of s form the first j of t.
• ✅ Set the first column to one. There is one way to form an empty t: delete all of s.
• ✅ You can always skip the current letter of s, giving dp[i-1][j].
• ✅ When letters match, also add dp[i-1][j-1] for using the letter.
• ✅ The answer sits in the bottom-right cell dp[len(s)][len(t)].

🚀 What’s Next?

• Interleaving String
• Target Sum