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 is the string s
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.
Input String contains only lowercase English Letters and string length is 5000 at maximum.
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 starts=i where 0<=i<m & startt=j where 0<=j<11
Now we have two options,
Now we have only one option which is check for starts+1, startt as 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.
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.
Output:need an explanation for this answer? contact us directly to get an explanation for this answer