Home »
Interview coding problems/challenges
Find number of times a string occurs as a subsequence
Here, we are going to learn the solution to find number of times a string occurs as a subsequence – which is a popular interview question based on dynamic programming.
Submitted by Radib Kar, on February 15, 2020
Description
It's a popular interview question based of dynamic programming which has been already featured in Accolite, Amazon.
Problem statement
Given two strings S and T, find the number of times the second string occurs in the first string, whether continuous or discontinuous as subsequence.
Input:
String S: "iloveincludehelp"
String T: "il"
Output:
5
Explanation
The first string is,
The second string is "il"
First occurrence:
Second occurrence:
Third occurrence:
Fouth occurrence:
Fifth occurrence:
So, total distinct occurrences are 5.
Solution Approach
First, we discuss the recursive solution and then we will convert it to dynamic programming.
Prerequisite:
string s: the first string
string t: the second string
starts: start point of the first string
srartt: start point of the second string
m : length of first string
n : length of second string
How, how can we generate a recursive relation?
Say,
starts=i where i<m and i>=0 & start=j where j<n and j>=0
Say,

s[starts] = t[start] that means both have same character,
Now we have to option,
 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[start]
Now we have only one option which is check for starts+1, startt as we need to look for different occurrence only.
Function distinctOccurence(string s,string t,int starts,int startt,int m,int n)
if startt==n //enter substring is matched
return 1;
if starts==m //enter string has been searched with out match
return 0;
if(s[starts]!=t[startt])
//only one option as we discussed
return distinctOccurence(s,t,starts+1,startt,m,n);
else
//both the options as we discussed
return distinctOccurence(s,t,starts+1,startt+1,m,n) + distinctOccurence(s,t,starts+1,startt,m,n);
The above recursion will generate many overlapping subproblems and hence we need to use dynamic programming. (I would recommend to take two short string and try doing by your hand and draw the recursion tree to understand how recursion is working).
Let's convert the recursion to DP.
Step1: initialize DP table
int dp[m+1][n+1];
Step2: convert step1 of recursive function
for i=0 to n
dp[0][i]=0;
Step3: convert step2 of recursive function
for i=0 to m
dp[i][0]=1;
Step4: Fill the DP table which is similar to step3 of the recursion function
for i=1 to m
for j=1 to n
if s[i1]==t[j1]
dp[i][j]=dp[i1][j]+dp[i1][j1]
else
dp[i][j]=dp[i1][j]
end for
end for
Step5: return dp[m][n] which is the result.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
int distinctOccurence(string s, string t, int starts, int startt, int m, int n) {
//note argument k,l are of no use here
//initialize dp table
int dp[m + 1][n + 1];
//base cases
for (int i = 0; i <= n; i++)
dp[0][i] = 0;
for (int i = 0; i <= m; i++)
dp[i][0] = 1;
//fill the dp table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s[i  1] == t[j  1])
dp[i][j] = dp[i  1][j] + dp[i  1][j  1];
else
dp[i][j] = dp[i  1][j];
}
}
return dp[m][n];
}
int main() {
int n, m;
string s1, s2;
cout << "Enter the main string:\n";
cin >> s1;
cout << "Enter the substring:\n";
cin >> s2;
m = s1.length();
n = s2.length();
cout << s2 << " has " << distinctOccurence(s1, s2, 0, 0, m, n) << " times different occurences in " << s1 << endl;
return 0;
}
Output
Enter the main string:
iloveincludehelp
Enter the substring:
il
il has 5 times different occurences in iloveincludehelp