Count occurrences of a string that can be constructed from another given string in C++

We are given with two strings str_1 and str_2 as input. The goal is to find the count of strings same as str_2 that can be constructed using letters picked from str_1 from which each character is used just once.

Note − All alphabets in both are in the same case.

Let us understand with examples.

Input − str_1 = "abcaaaabca", str_2 = "bca";

Output − Count occurrences of a string that can be constructed from another given string are: 2

Explanation − Substrings bca in str_a −

str_1[1-3]=”bca” and str[7-9]=”bca”

Input − str_1 = "about", str_2 = "cout";

Output − Count occurrences of a string that can be constructed from another given string are − 0

Explanation − Substrings cout not present in str_a.

The approach used in the below program is as follows

We will first calculate the frequency of all alphabets in str_1 and store it in array arr_1[26] and store the frequency of all alphabets in arr_2 in array arr_2[26].

• Take two strings str_1 and str_2. Calculate the length as str_1.size() andstr_2.size().

• Function count_string(string str_1, int len_str_1, string str_2, int len_str_2) takes both strings and lengths and returns a number of strings str_2 that can be constructed from str_1.

• Take initial count as INT_MAX.

• Initialize two arrays arr_1[26] for the frequency of characters in str_1 and arr_2[26] for the frequency of characters in arr_2 with 0.

• Traverse both str_1 and str_2 using for loop and update frequencies in arr_1 and arr_2.

• Now traverse arr_2 again using for loop and if current frequency arr_2[i] is non zero then minimum of count(previous value) and arr_1[i]/arr_2[i] ( taking each alphabet from str_1 only once for each character of str_2 ).

• In the end, count will have a minimum value of matched corresponding characters of str_1 and str_2. example aaabbbb (a=3,b=4) and abb(a=1,b=2) minimum count will be 1

• Return count at the end of all loops as the desired result.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; int count_string(string str_1, int length_str_1, string str_2, int length_str_2){    int count = INT_MAX;    int arr_1[26] = { 0 };    int arr_2[26] = { 0 };    for (int i = 0; i < length_str_1; i++){       arr_1[str_1[i] - 'a']++;    }    for (int i = 0; i < length_str_2; i++){       arr_2[str_2[i] - 'a']++;    }    int total_alphabets = 26;    for (int i = 0; i < total_alphabets; i++){       if(arr_2[i]){          count = min(count, arr_1[i] / arr_2[i]);       }    }    return count; } int main(){    string str_1 = "knowledge", str_2 = "know";    int length_str_1 = str_1.size();    int length_str_2 = str_2.size();    cout<<"Count occurrences of a string that can be constructed from another given string are: "<<count_string(str_1,length_str_1, str_2, length_str_2);    return 0; }

Output

If we run the above code it will generate the following output −

Count occurrences of a string that can be constructed from another given string are: 1