Distinct Subsequences

Share

Given strings s and t, return the number of distinct subsequences of s which equals t.

Example 1
Input: s="rabbbit", t="rabbit" → Output: 3
Example 2
Input: s="babgbag", t="bag" → Output: 5

Solution Approach

dp[i][j] = number of ways to form t[0..j-1] from s[0..i-1]. If s[i-1]==t[j-1]: dp[i][j] = dp[i-1][j-1] + dp[i-1][j]. Else: dp[i][j] = dp[i-1][j].

  • dp[i][0] = 1 (empty t matched by any prefix of s).
  • dp[0][j] = 0 for j > 0.
  • Fill table: if match, add both using current s char and skipping it.
  • 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];
    }
}
  • Time Complexity: O(M*N)
  • Space Complexity: O(M*N)