Q:

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

belongs to collection: interview C++ coding problems/challenges | dynamic programming

mahmoud2506

Save to bookmark

|

2022-04-30

|

556

0

Find number of times a string occurs as a subsequence

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,

Find number of times a string occurs as a subsequence (1)

The second string is "il"

First occurrence:

Find number of times a string occurs as a subsequence (2)

Second occurrence:

Find number of times a string occurs as a subsequence (2)

Third occurrence:

Find number of times a string occurs as a subsequence (2)

Fouth occurrence:

Find number of times a string occurs as a subsequence (2)

Fifth occurrence:

Find number of times a string occurs as a subsequence (2)

So, total distinct occurrences are 5.

C++ programming, Interview questions, C++ programming Interview-questions,

login and add your own answer to this question

All Answers

mahmoud2506

2022-04-30

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

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,
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.
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[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]
            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

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

total answers (1)

Given a number n, we can divide it into only three... >>

<< Given a M X N matrix with initial position at top-...