Let the input string be, s and t="includehelp"

This problem can be solved by recursion.

So we have,
string s: the input string
string t: the second string ("includehelp")
starts  : start point of string s
srartt  : start point of string t, ("includehelp")

m: length of input string
11: length of string t,"includehelp"

MOD: 1000000009

Now, how can we generate a recursive relation?

Say starts=i where 0<=i<m & startt=j where 0<=j<11

Say,

1. s[starts]=t[startt] that means both have same character,
   Now we have two options,
   1. Check for starts+1, startt+1 which means we are looking for the same occurrence, we want to check for other characters as well.
   2. Check for starts+1, startt which means we are looking for another different occurrence.
2. s[starts]!=t[startt]
   Now we have only one option which is check for starts+1, startt as we need to look for different occurrence only.

Function:
jumbleString(string s,string t,int starts,int startt,int m)
// enter substring is matched
if startt==11
    return 1;
    
// enter string has been searched with out match 
if starts==m
    return 0;
    
if(s[starts]!=t[startt])
    //only one option as we discussed
    return jumbleString(s,t,starts+1,startt,m)%MOD;
else
    // both the options as we discussed
    return (jumbleString(s,t,starts+1,startt+1,m)%MOD +
            jumbleString(s,t,starts+1,startt,m)%MOD)%MOD

The above recursion will generate many overlapping subproblems and hence we need to use dynamic programming.

Let's convert the recursion to DP.

• Step 1: initialize DP table,

  int dp[m+1][12];
  

• Step 2: convert step1 of recursive function,

  for i=0 to 11
      dp[0][i]=0;
  

• Step 3: convert step 2 of recursive function,

  for i=0 to m
      dp[i][0]=1;
  

• Step 4: Fill the DP table which is similar to step3 of the recursion function,

  for i=1 to m
      for j=1 to 11
          if s[i-1]==t[j-1]
              dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%MOD
          else
              dp[i][j]=dp[i-1][j]
      end for
  end for
  

• Step5: return 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:

#include <bits/stdc++.h>
using namespace std;

int dp[1001][12];

int jumbled(string s1, string s2, int i, int j, int n, int m)
{

    if (j == m) {
        return 1;
    }
    if (i == n && j != m)
        return 0;

    // if subproblem already solved
    if (dp[i][j] != -1) 
        return dp[i][j];

    if (s1[i] == s2[j]) {
        dp[i][j] = jumbled(s1, s2, i + 1, j + 1, n, m) + jumbled(s1, s2, i + 1, j, n, m);
    }
    else {
        dp[i][j] = jumbled(s1, s2, i + 1, j, n, m);
    }

    return dp[i][j];
}

int main()
{
    int n;
    
    string s2 = "includehelp";
    
    string s1;
    cout << "Input string: ";
    cin >> s1;
    
    n = s1.length();
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 11; j++)
            dp[i][j] = -1;
    }

    cout << "We can jumble " << jumbled(s1, s2, 0, 0, n, 11) << " of ways." << endl;

    return 0;
}

Output:

Input string: iincludehelp
We can jumble 2 of ways.