हमें इनपुट के रूप में दो स्ट्रिंग str_1 और str_2 दी गई हैं। लक्ष्य str_2 के समान उन स्ट्रिंग की संख्या ज्ञात करना है जिन्हें str_1 से अक्षर चुनकर बनाया जा सकता है जिसमें प्रत्येक वर्ण का उपयोग केवल एक बार किया जाता है।
नोट - दोनों में सभी वर्णमाला समान केस में हैं।
उदाहरण सहित समझ
इनपुट - str_1 = "abcaaaabca", str_2 = "bca";
आउटपुट - दूसरी दी गई स्ट्रिंग से बनाई जा सकने वाली स्ट्रिंग की घटनाओं की संख्या: 2
व्याख्या - str_a में सबस्ट्रिंग bca:
str_1[1-3]="bca" और str[7-9]="bca"
इनपुट - str_1 = "about", str_2 = "cout";
आउटपुट - दूसरी दी गई स्ट्रिंग से बनाई जा सकने वाली स्ट्रिंग की घटनाओं की संख्या: 0
व्याख्या - str_a में सबस्ट्रिंग cout मौजूद नहीं है।
प्रोग्राम में उपयोग किया गया दृष्टिकोण
हम पहले str_1 में सभी वर्णमाला की आवृत्ति की गणना करेंगे और इसे सरणी arr_1[26] में संग्रहीत करेंगे और arr_2 में सभी वर्णमाला की आवृत्ति को सरणी arr_2[26] में संग्रहीत करेंगे।
- दो स्ट्रिंग
str_1औरstr_2लें। लंबाई की गणनाstr_1.size()औरstr_2.size()के रूप में करें। - फंक्शन
count_string(string str_1, int len_str_1, string str_2, int len_str_2)दोनों स्ट्रिंग और लंबाई लेता है औरstr_1से बनाई जा सकने वालीstr_2की संख्या लौटाता है। - प्रारंभिक काउंट
INT_MAXके रूप में लें। arr_1[26]कोstr_1में वर्णों की आवृत्ति के लिए औरarr_2[26]कोarr_2में वर्णों की आवृत्ति के लिए 0 से आरंभ करें।- फॉर लूप का उपयोग करके
str_1औरstr_2दोनों को ट्रैवर्स करें औरarr_1औरarr_2में आवृत्तियों को अपडेट करें। - अब फॉर लूप का उपयोग करके
arr_2को फिर से ट्रैवर्स करें और यदि वर्तमान आवृत्तिarr_2[i]शून्येतर है तोcount(पिछला मान) औरarr_1[i]/arr_2[i]का न्यूनतम (str_1से प्रत्येक वर्णमाला कोstr_2के प्रत्येक वर्ण के लिए केवल एक बार लेना )। - अंत में, काउंट में
str_1औरstr_2के मिलान वाले संबंधित वर्णों का न्यूनतम मान होगा। उदाहरण aaabbbb (a=3,b=4) और abb (a=1,b=2) न्यूनतम काउंट 1 होगा। - सभी लूप के अंत में परिणाम के रूप में काउंट लौटाएँ।
उदाहरण
#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;
}
आउटपुट
Count occurrences of a string that can be constructed from another given string are: 1
