Skip to main content

Distinct SubSequence

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​

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.

Institution​

The problem is to find the number of distinct subsequences of string s that equal string t. This can be thought of as a dynamic programming problem where we keep track of the number of ways to form the substring t using the substring of s.

Approach​

  • We use a dynamic programming table dp where dp[i][j] represents the number of distinct subsequences of the first i characters of s that equal the first j characters of t.

Initialization:

  • If t is empty, there is exactly one subsequence of s that matches t (the empty subsequence). Hence, dp[i][0] = 1 for all i.

  • If s is empty but t is not, no subsequences of s can match t. Hence, dp[0][j] = 0 for all j > 0. Filling the DP Table:

  • If s[i-1] == t[j-1], then the number of ways to form t[0..j-1] from s[0..i-1] is the sum of:

  • The number of ways to form t[0..j-1] from s[0..i-2] (excluding the current character of s).

  • The number of ways to form t[0..j-2] from s[0..i-2] (including the current character of s).

  • If s[i-1] != t[j-1], then the number of ways to form t[0..j-1] from s[0..i-1] is the same as the number of ways to form t[0..j-1] from s[0..i-2] (excluding the current character of s).

Code in C++​

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<unsigned long long>> dp(s.size()+1,vector<unsigned long long>(t.size()+1,0));
        
        for(int i=0;i<=s.size();i++){
            dp[i][0]=1;
        }
        // for(int j=1;j<=t.size();j++){
        //     dp[0][j]=0;
        // }

        for(int i=1;i<=s.size();i++){
            for(int j=1;j<=t.size();j++){
                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];
                }
            }
        }
        return dp[s.size()][t.size()];

        
    }
};

Code in Java​

class Solution {
    public int numDistinct(String s, String t) {
        int l1 = s.length();
        int l2 = t.length();
        
        int[] dp = new int[l2+1];
        
        for(int i = 0; i <= l1; i++){
            
            for(int j = l2; j >= 0; j--){
                if(j == 0){
                    dp[j] = 1;
                }
                else if(i == 0){
                    dp[j] = 0;
                }                
                else{
                    int notPick = dp[j];
                    int pick = 0;
                    if(s.charAt(i-1) == t.charAt(j-1)){
                        pick = dp[j - 1];
                    }
                    dp[j] = pick + notPick;
                }
            }
        }
        
        return dp[l2];
	}
}

Complexity Analysis​

  • Time complexity: O(n×m)

  • Space complexity: O(n×m)