Distinct Subsequences

Problem Description

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

Constraints

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

State Transition and Space Optimization

Let dp[i][j] be the number of distinct subsequences of s[0..i-1] that equal t[0..j-1]. We look at s[i - 1] and t[j - 1]:

• Option A (Skip): we can always choose to skip character s[i - 1]. The count of ways is dp[i - 1][j].
• Option B (Match): if s[i - 1] == t[j - 1], we can choose to match them. The count of ways is dp[i - 1][j - 1].

Thus, 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]

Base case: dp[i][0] = 1 for all i (there is exactly 1 way to form the empty string t = "": by deleting all characters of s).

We can optimize space to a 1D array dp of size t.length() + 1 by updating from right to left (so that dp[j - 1] from the previous row is not overwritten before we use it).

Solution: 1D DP Array (Right-to-Left)

class Solution {
    public int numDistinct(String s, String t) {
        int n = s.length(), m = t.length();
        if (n < m) return 0;

        int[] dp = new int[m + 1];
        dp[0] = 1; // base case: empty target

        for (int i = 1; i <= n; i++) {
            char sChar = s.charAt(i - 1);
            // loop backwards to use values from the previous iteration
            for (int j = m; j >= 1; j--) {
                if (sChar == t.charAt(j - 1)) {
                    dp[j] += dp[j - 1];
                }
            }
        }

        return dp[m];
    }
}

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        if n < m:
            return 0

        dp = [0] * (m + 1)
        dp[0] = 1

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

        return dp[m]

#include <vector>
#include <string>

class Solution {
public:
    int numDistinct(std::string s, std::string t) {
        int n = s.length(), m = t.length();
        if (n < m) return 0;

        // use unsigned long long to prevent intermediate overflow before target sum check in C++
        std::vector<unsigned long long> dp(m + 1, 0);
        dp[0] = 1;

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

        return dp[m];
    }
};

Complexity Analysis:

• Time Complexity: O(N * M) where N is the length of s and M is the length of t.
• Space Complexity: O(M) to store the 1D DP array.

← All Problems