Given a pattern, count number of times the pattern appears in the given string as a subsequence.

Input:

string = “subsequence”;

pattern = “sue”;

Output: 7

subsequence

subsequence

subsequence

subsequence

subsequence

subsequence

subsequence

The idea is to use recursion to solve this problem. If we compare the last character of the string X[0..m] with last character of the pattern Y[0..n], there are two possibilities –

1. If the last character of the string is same as the last character of the pattern, we recuse for the remaining substring X[0..m-1] and Y[0..n-1]. Since we want all possible combinations, we also consider the case when current character of string do not form part of the solution. i.e. we ignore the last character of the string and recurse for the remaining substring X[0..m-1].

2. If last character of the string is different from the last character of the pattern, then we ignore the last character of the string and recurse for the remaining substring X[0..m-1]

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <iostream> using namespace std; // Function to count number of times the pattern Y[0..n) // appears in given string X[0..m) as a subsequence int count(string X, string Y, int m, int n) { // Base case 1: if only one character is left if (m == 1 && n == 1) return (X[0] == Y[0]); // Base case 2: if input string X reaches its end, if (m == 0) return 0; // Base case 3: if pattern Y reaches its end, we have found subsequence if (n == 0) return 1; // Optimization: Solution is not possible if number of characters // in the string is less than number of characters in the pattern if (n > m) return 0; // if last character of both string and pattern matches, // 1. exclude last character in both string and pattern // 2. exclude only last character in the string // else if last character of string and pattern do not match, // recurse by excluding only last character in the string return ((X[m-1] == Y[n-1]) ? count(X, Y, m - 1, n - 1) : 0) + count(X, Y, m - 1, n); } // main function int main() { string X = "subsequence"; // input string string Y = "sue"; // pattern cout << count(X, Y, X.size(), Y.size()); return 0; } |

**Output: **

7

The time complexity of above solution is exponential and auxiliary space used by the program is O(1).

The idea is to use Dynamic Programming to solve this problem. The problem has an **optimal substructure**. Above solution also exhibits **overlapping subproblems**. If we draw the recursion tree of the solution, we can see that the same sub-problems are getting computed again and again. We know that problems having optimal substructure and overlapping subproblems can be solved by using dynamic programming, in which subproblem solutions are memoized rather than computed again and again. The *Memo*ized version follows the top-down approach, since we first break the problem into subproblems and then calculate and store values. We can also solve this problem in bottom-up manner. In the bottom-up approach, we solve smaller sub-problems first, then solve larger sub-problems from them. The approach is illustrated below –

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include <iostream> using namespace std; // Function to count number of times the pattern Y[0..n) // appears in given string X[0..m) as a subsequence int count(string X, string Y, int m, int n) { // T[i][j] stores number of of times the pattern Y[0..j) // appears in given string X[0..i) as a subsequence int T[m + 1][n + 1]; // if pattern Y is empty, we have found subsequence for (int i = 0; i <= m; i++) T[i][0] = 1; // if input string X is empty for (int j = 1; j <= n; j++) T[0][j] = 0; // if current character of both string and pattern matches, // 1. exclude current character in both string and pattern // 2. exclude only current character in the string // else if current character of string and pattern do not match, // exclude current character in the string for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) T[i][j] = ((X[i-1] == Y[j-1]) ? T[i-1][j-1] : 0) + T[i-1][j]; // return last entry in lookup table return T[m][n]; } // main function int main() { string X = "subsequence"; // input string string Y = "sue"; // pattern cout << count(X, Y, X.size(), Y.size()) << endl; return 0; } |

**Output: **

7

The time complexity of above solution is O(mn) and auxiliary space used by the program is O(mn).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂