LeetCode Hard – Distinct Subsequences

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.

Example 1:

Input: s = “rabbbit”, t = “rabbit”

Output: 3

Explanation: As shown below, there are 3 ways you can generate “rabbit” from s. rabbbitrabbbitrabbbit

Example 2:

Input: s = “babgbag”, t = “bag”

Output: 5

Explanation: As shown below, there are 5 ways you can generate “bag” from s. babgbagbabgbagbabgbagbabgbagbabgbag

Constraints:

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

Java Solution

To solve this problem, you can use dynamic programming to build a table where dp[i][j] represents the number of distinct subsequences of the first i characters of s that match the first j characters of t. The recurrence relation is based on whether the current characters of s and t match or not. Here’s the Java solution:

public class DistinctSubsequences {
    public static int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();

        // dp[i][j] represents the number of distinct subsequences of s[0...i-1] that match t[0...j-1]
        int[][] dp = new int[m + 1][n + 1];

        // Initializing base cases
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1; // An empty string is a subsequence of any string
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // If the current characters match, we can choose to include or exclude the current character in s
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    // If they don't match, we can only exclude the current character in s
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[m][n];
    }

    public static void main(String[] args) {
        System.out.println(numDistinct("rabbbit", "rabbit"));  // Output: 3
        System.out.println(numDistinct("babgbag", "bag"));      // Output: 5
    }
}

This Java code uses a two-dimensional array dp to store the number of distinct subsequences. The base cases initialize the first column, representing an empty string as a subsequence. The recurrence relation is based on whether the current characters match or not. The final result is stored in dp[m][n], where m is the length of string s and n is the length of string t.

Python Solution

def numDistinct(s, t):
    m, n = len(s), len(t)

    # dp[i][j] represents the number of distinct subsequences of s[0...i-1] that match t[0...j-1]
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Initializing base cases
    for i in range(m + 1):
        dp[i][0] = 1  # An empty string is a subsequence of any string

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # If the current characters match, we can choose to include or exclude the current character in s
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
            else:
                # If they don't match, we can only exclude the current character in s
                dp[i][j] = dp[i - 1][j]

    return dp[m][n]

# Test cases
print(numDistinct("rabbbit", "rabbit"))  # Output: 3
print(numDistinct("babgbag", "bag"))      # Output: 5

This Python code follows the same logic as the Java solution. It uses a two-dimensional array dp to store the number of distinct subsequences. The base cases initialize the first column, representing an empty string as a subsequence. The recurrence relation is based on whether the current characters match or not. The final result is stored in dp[m][n], where m is the length of string s and n is the length of string t.