Distinct Subsequences

Problem

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.

Examples

Example 1

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
rabbbit
rabbbit

Example 2

Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from s.
babgbag
babgbag
babgbag
babgbag
babgbag

Solution

Method 1 – Top-Down Dynamic Programming (Memoization)

Intuition

We recursively try to match each character of t with s, exploring both possibilities: using the current character of s or skipping it. Memoization avoids recomputation by storing results for subproblems.

Approach

1. Define a recursive function dfs(i, j) that returns the number of ways to form t[j:] from s[i:].
2. If j reaches the end of t, return 1 (found a valid subsequence).
3. If i reaches the end of s but j hasn't reached the end of t, return 0 (not possible).
4. If s[i] == t[j], two choices:

• Use s[i] to match t[j] and move both pointers.
• Skip s[i] and only move i.

5. If s[i] != t[j], skip s[i] and move i.
6. Use memoization to cache results for each (i, j).

Code

C++

class Solution {
public:
   int numDistinct(string s, string t) {
      int m = s.size(), n = t.size();
      vector<vector<int>> memo(m, vector<int>(n, -1));
      function<int(int, int)> dfs = [&](int i, int j) -> int {
        if (j == n) return 1;
        if (i == m) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        int ans = dfs(i + 1, j);
        if (s[i] == t[j]) ans += dfs(i + 1, j + 1);
        return memo[i][j] = ans;
      };
      return dfs(0, 0);
   }
};

Go

func numDistinct(s string, t string) int {
   m, n := len(s), len(t)
   memo := make([][]int, m)
   for i := range memo {
      memo[i] = make([]int, n)
      for j := range memo[i] {
        memo[i][j] = -1
      }
   }
   var dfs func(i, j int) int
   dfs = func(i, j int) int {
      if j == n {
        return 1
      }
      if i == m {
        return 0
      }
      if memo[i][j] != -1 {
        return memo[i][j]
      }
      ans := dfs(i+1, j)
      if s[i] == t[j] {
        ans += dfs(i+1, j+1)
      }
      memo[i][j] = ans
      return ans
   }
   return dfs(0, 0)
}

Java

class Solution {
   public int numDistinct(String s, String t) {
      int m = s.length(), n = t.length();
      Integer[][] memo = new Integer[m][n];
      return dfs(s, t, 0, 0, memo);
   }
   private int dfs(String s, String t, int i, int j, Integer[][] memo) {
      if (j == t.length()) return 1;
      if (i == s.length()) return 0;
      if (memo[i][j] != null) return memo[i][j];
      int ans = dfs(s, t, i + 1, j, memo);
      if (s.charAt(i) == t.charAt(j)) {
        ans += dfs(s, t, i + 1, j + 1, memo);
      }
      memo[i][j] = ans;
      return ans;
   }
}

Kotlin

class Solution {
   fun numDistinct(s: String, t: String): Int {
      val m = s.length
      val n = t.length
      val memo = Array(m) { IntArray(n) { -1 } }
      fun dfs(i: Int, j: Int): Int {
        if (j == n) return 1
        if (i == m) return 0
        if (memo[i][j] != -1) return memo[i][j]
        var ans = dfs(i + 1, j)
        if (s[i] == t[j]) ans += dfs(i + 1, j + 1)
        memo[i][j] = ans
        return ans
      }
      return dfs(0, 0)
   }
}

Python

class Solution:
   def numDistinct(self, s: str, t: str) -> int:
      m, n = len(s), len(t)
      memo: dict[tuple[int, int], int] = {}
      def dfs(i: int, j: int) -> int:
        if j == n:
           return 1
        if i == m:
           return 0
        if (i, j) in memo:
           return memo[(i, j)]
        ans: int = dfs(i + 1, j)
        if s[i] == t[j]:
           ans += dfs(i + 1, j + 1)
        memo[(i, j)] = ans
        return ans
      return dfs(0, 0)

Rust

impl Solution {
   pub fn num_distinct(s: String, t: String) -> i32 {
      fn dfs(
        s: &[u8], t: &[u8], i: usize, j: usize, memo: &mut Vec<Vec<Option<i32>>>
      ) -> i32 {
        if j == t.len() { return 1; }
        if i == s.len() { return 0; }
        if let Some(val) = memo[i][j] { return val; }
        let mut ans = dfs(s, t, i + 1, j, memo);
        if s[i] == t[j] {
           ans += dfs(s, t, i + 1, j + 1, memo);
        }
        memo[i][j] = Some(ans);
        ans
      }
      let m = s.len();
      let n = t.len();
      let mut memo = vec![vec![None; n]; m];
      dfs(s.as_bytes(), t.as_bytes(), 0, 0, &mut memo)
   }
}

Method 2 – Dynamic Programming (2D DP Table)

Intuition

We use dynamic programming to count the number of ways to form the target string t as a subsequence of the source string s. For each character in s, we decide whether to match it with the current character in t or skip it, accumulating the total number of ways.

Approach

1. Let dp[i][j] be the number of ways to form the first j characters of t from the first i characters of s.
2. Initialize dp[0][0] = 1 (empty t from empty s), and dp[i][0] = 1 for all i (empty t from any prefix of s).
3. For each i from 1 to len(s) and each j from 1 to len(t):

• If s[i-1] == t[j-1], then dp[i][j] = dp[i-1][j-1] + dp[i-1][j].
• Else, dp[i][j] = dp[i-1][j].

4. The answer is dp[len(s)][len(t)].

Code

C++

class Solution {
public:
   int numDistinct(string s, string t) {
      int m = s.size(), n = t.size();
      vector<vector<long long>> dp(m + 1, vector<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];
   }
};

Go

func numDistinct(s string, t string) int {
   m, n := len(s), len(t)
   dp := make([][]int, m+1)
   for i := range dp {
      dp[i] = make([]int, n+1)
      dp[i][0] = 1
   }
   for i := 1; i <= m; i++ {
      for 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 dp[m][n]
}

Java

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];
   }
}

Kotlin

class Solution {
   fun numDistinct(s: String, t: String): Int {
      val m = s.length
      val n = t.length
      val dp = Array(m + 1) { LongArray(n + 1) }
      for (i in 0..m) dp[i][0] = 1L
      for (i in 1..m) {
        for (j in 1..n) {
           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].toInt()
   }
}

Python

class Solution:
   def numDistinct(self, s: str, t: str) -> int:
      m, n = len(s), len(t)
      dp: list[list[int]] = [[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]

Rust

impl Solution {
   pub fn num_distinct(s: String, t: String) -> i32 {
      let (m, n) = (s.len(), t.len());
      let s = s.as_bytes();
      let t = t.as_bytes();
      let mut dp = vec![vec![0i64; n + 1]; m + 1];
      for i in 0..=m { dp[i][0] = 1; }
      for i in 1..=m {
        for j in 1..=n {
           dp[i][j] = dp[i-1][j];
           if s[i-1] == t[j-1] {
              dp[i][j] += dp[i-1][j-1];
           }
        }
      }
      dp[m][n] as i32
   }
}

Complexity

• ⏰ Time complexity: O(m * n), where m = len(s), n = len(t)
• 🧺 Space complexity: O(m*n), for memoization stack and cache