# Distinct Subsequences

A subsequence is a sequence obtained from another by the exclusion of a number of elements.
Note : The relative order of elements in a subsequence remains the same as that of the original sequence.

Example of a subsequence in a given sequence
Sequence: [ S, U, N, D, A, Y]
Subsequence 1: [ S, U, N ]
Subsequence 2: [ S, A, Y ]
Subsequence 3: [ D, A, Y ]

Finding number of distinct subsequences in a source string matching the target string.

``````#include<iostream>
#include<map>
#include<string>
#include<vector>

using namespace std;

class DistinctSubsequences {

public:
map<pair<string,string>, int> table;

int NumDistinct (string src, string target) {

if (src.size() < target.size()) {
return 0;
}

if (table.find (make_pair (src, target)) != table.end()) {
return table[make_pair (src, target)];
}

int ways = 0;

if (src.empty() && target.empty()) {
return 1;
} else if (src.empty() == false and target.empty() == true) {
return 1;
} else if (src.empty() == true and target.empty() == false) {
return 0;
} else if (src.at(0) == target.at(0)) {
ways += NumDistinct (src.substr(1), target.substr(1));
ways += NumDistinct (src.substr(1), target);
} else {
ways += NumDistinct (src.substr(1), target);
}

table[make_pair(src, target)] = ways;
return ways;
}
};

int main() {

DistinctSubsequences ds;

vector<string> src = { "abab", "babgbag", "rabbbit", "sunnylion", "willbbertt" };
vector<string> target = { "ab", "bag", "rabbit", "sun", "wilbert" };

for (int i=0; i<src.size(); i++) {
cout << "Number of distinct subsequences of " << src[i] << " which equal " << target[i] << " : " << ds.NumDistinct(src[i], target[i]) << endl;
}
return 0;
}
``````

Output

``````Number of distinct subsequences of abab which equal ab : 3
Number of distinct subsequences of babgbag which equal bag : 5
Number of distinct subsequences of rabbbit which equal rabbit : 3
Number of distinct subsequences of sunnylion which equal sun : 3
Number of distinct subsequences of willbbertt which equal wilbert : 8
``````