Distinct Subsequences

Problem Statement

The task is to determine the number of distinct subsequences of a given string s that match exactly another string t. A subsequence of a string is a new string generated from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. For instance, "ace" is a subsequence of "abcde". We aim to find all such subsequences of s that are identical to t. This problem ensures that the solution remains within the bounds of 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

Constraints

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

Approach and Intuition

To solve this problem, a dynamic programming approach is very relevant:

1. Define a 2D array dp where dp[i][j] represents the count of distinct subsequences of s[0...i-1] (the substring of s from start to index i-1 inclusive) that equals t[0...j-1].
2. Initialize dp[0][0] to 1 because an empty substring of s matches an empty substring of t in exactly one way.
3. Initialize dp[i][0] to 1 for all i >= 1; any part of s (including the whole string) contains the empty string t exactly once as a subsequence.
4. For all other positions, compute dp[i][j] based on two conditions:
   • If characters s[i-1] and t[j-1] are the same, update dp[i][j] based on counting these subsequences by including s[i-1] as part of the subsequence (dp[i-1][j-1]) and ignoring s[i-1] (dp[i-1][j]).
   • If characters s[i-1] and t[j-1] are not the same, then dp[i][j] is entirely based on ignoring s[i-1] (dp[i-1][j]).

Let's walk through aspects of the examples to clarify:

• In Example 1 with s = "rabbbit" and t = "rabbit": By evaluating different matching scenarios, such as considering every character's occurrence and possibility in s for use in a matching sequence, we get three distinct ways to form "rabbit".

• In Example 2 with s = "babgbag" and t = "bag": The pattern "bag" can be created in numerous ways by skipping different characters in s while maintaining relative order, leading to five different sequences.

The above approach calculates the answer by efficiently using prior computed values. This strategy emphasizes the power of dynamic programming in reducing redundant computations, especially in counting problems involving subsequences. It ensures that our solution is quantifiable and adaptable to input scales defined by the constraints.

Solutions

class Solution {
public:
    int countSubsequences(string str1, string str2) {
        int len1 = str1.length();
        int len2 = str2.length();
        vector<vector<unsigned int>> dpTable(len1 + 1, vector<unsigned int>(len2 + 1));
        for (int i = 0; i <= len1; i++) {
            dpTable[i][len2] = 1;
        }
        for (int j = len2 - 1; j >= 0; j--) {
            for (int i = len1 - 1; i >= 0; i--) {
                if (str1[i] == str2[j]) {
                    dpTable[i][j] = dpTable[i + 1][j + 1] + dpTable[i + 1][j];
                } else {
                    dpTable[i][j] = dpTable[i + 1][j];
                }
            }
        }
        return dpTable[0][0];
    }
};