Recursion: Given a string and a sub-string, count the number of occurrence recursively.

Coding Interview Questions

1 min read

Problem Statement:

You are given a string and sub-string.

You need to find the occurrence of the sub-string recursively.

Example:

Input:

str1 = "proDevelopertutorialpro"
str2 = "pro"

Output: 2

Solution Explanation:

If the size of substring is greater than the string, then return 0.

Else, check if str2 is present in str1, if yes, then increment count and return the result.

Time Complexity: O(n2)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <string>
using namespace std;

int solution(string str1, string str2)
{
    int n1 = str1.length();
    int n2 = str2.length();

    // base Case
    if (n1 == 0 || n1 < n2)
        return 0;

    if (str1.substr(0, n2).compare(str2) == 0)
        return solution(str1.substr(1), str2) + 1;

    return solution(str1.substr(1), str2);
}


int main()
{
    string str1 = "proDevelopertutorialpro", str2 = "pro";
    cout << solution(str1, str2) << endl;

    return 0;
}