Home »
Interview coding problems/challenges
Jumbled Strings
Jumbled Strings: In this article, we are going to see a recursive problem (Jumbled Strings) and its solution that can be featured in any interview rounds.
Submitted by Radib Kar, on June 07, 2020
Problem statement:
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.
Solution Approach:
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,

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

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.
The above DP technique is known as the tabulation process. We can introduce memorization as well, known as the topdown approach. Where we store every computed subproblem and while computing first we look up our DP table whether subproblem is already solved or not. Check the below topdown 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.
TOP Interview Coding Problems/Challenges