Distinct Subsequences in C++

Suppose we have strings S and T. We have to count number of distinct sequences of S which is equal to T.

We know that a subsequence of a string is a new string which is formed from the original string by removing some (can be none) of the characters without disturbing the relative positions of the remaining characters. (Like, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

If the input strings are “baalllloonnn” and “balloon”, then there will be 36 different ways to select.

To solve this, we will follow these steps −

• n := size of s, m := size of t. Update s and t by concatenating blank spaces before them

• Make one matrix of size (n + 1) x (m + 1)

• set dp[0, 0] := 1, then set 1 for 0th column of all row, put 1

• for i in range 1 to n

  • for j in range 1 to m

    • if s[i] = t[j], then

      • dp[i, j] := dp[i – 1, j – 1]

    • dp[i, j] := dp[i, j] + dp[i – 1, j]

• return dp[n, m]

Example

Let us see the following implementation to get better understanding −

 Live Demo

#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution {    public:    int numDistinct(string s, string t) {       int n = s.size();       int m = t.size();       s = " " + s;       t = " " + t;       vector < vector <lli>> dp(n + 1, vector <lli> (m + 1));       dp[0][0] = 1;       for(int i = 1; i<= n; i++)dp[i][0] = 1;       for(int i = 1; i <= n; i++){          for(int j = 1; j <= m; j++){             if(s[i] == t[j]) dp[i][j] = dp[i - 1][j - 1];             dp[i][j]+= dp[i - 1][j];          }       }       return dp[n][m];    } }; main(){    Solution ob;    cout << (ob.numDistinct("baalllloonnn", "balloon")); }

Input

"baalllloonnn" "balloon"

Output

36