# Jumbled Strings

You are provided an input string **S** and the string "includehelp". You need to figure out all possible subsequences "includehelp" in the string **S**? Find out the number of ways in which the subsequence "includehelp" can be formed from the string **S**.

**Input:**

Input is the string **s**

**Output:**

Corresponding to each test case, print in a new line, a number denoting the number of ways in which we can form the subsequence "includehelp". Since output can be very large find the answer modulo **1000000007**.

**Constraints:**

Input String contains only lowercase English Letters and string length is 5000 at maximum.

**Example:**

Input:
includehelp
Output:
1
Explanation:
There is only one instances of "includehelp"
in the above input string.
Input:
iincludehelp
Output:
2
Explanation:
There is two instances of "includehelp"
in the above input string.

Now, how can we generate a recursive relation?

Say

wherestarts=iwhere0<=i<m & startt=j0<=j<11Say,

Now we have two options,

starts+1,startt+1which means we are looking for the same occurrence, we want to check for other characters as well.starts+1,starttwhich means we are looking for another different occurrence.s[starts]!=t[startt]Now we have only one option which is check for

starts+1,starttas we need to look for different occurrence only.The above recursion will generate many overlapping subproblems and hence we need to use dynamic programming.

Let's convert the recursion to DP.

dp[m][11]which is the result.The above DP technique is known as the tabulation process. We can introduce memorization as well, known as the top-down approach. Where we store every computed subproblem and while computing first we look up our DP table whether sub-problem is already solved or not. Check the below top-down implementation for the above problem.

C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: