আমাদের দুটি স্ট্রিং str_1 এবং str_2 ইনপুট হিসেবে দেওয়া আছে। লক্ষ্য হলো str_2 এর মত কতগুলো স্ট্রিং str_1-এর অক্ষরগুলো ব্যবহার করে তৈরি করা যায়, যেখানে প্রতিটি অক্ষর শুধু একবার ব্যবহার করা যাবে।
নোট − দুটি স্ট্রিং-এ সব অক্ষার কেস একই।
উদাহরণ দিয়ে বুঝি
ইনপুট − str_1 = "abcaaaabca", str_2 = "bca"
আউটপুট − অন্য স্ট্রিং থেকে তৈরি হয় এমন স্ট্রিং সংখ্যা: ২
ব্যাখ্যা − str_1-এ "bca" সাবস্ট্রিং: str_1[1-3]="bca" এবং str[7-9]="bca"
ইনপুট − str_1 = "about", str_2 = "cout"
আউটপুট − অন্য স্ট্রিং থেকে তৈরি হয় এমন স্ট্রিং সংখ্যা: ০
ব্যাখ্যা − str_1-এ "cout" নেই।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
প্রথমে str_1-এর সব অ্যালফাবেটের ফ্রিকোয়েন্সি বের করে arr_1[26]-এ রাখব। str_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_2কতবার তৈরি করা যায় সেটা রিটার্ন করে।- প্রাথমিক কাউন্ট
INT_MAX। - দুটি অ্যারে
arr_1[26](str_1-এর ফ্রিকোয়েন্সি) এবংarr_2[26](str_2-এর ফ্রিকোয়েন্সি) ০ দিয়ে ইনিশিয়ালাইজ। str_1এবংstr_2ট্রাভার্স করে ফ্রিকোয়েন্সি আপডেট করুন।arr_2আবার ট্রাভার্স করুন: যদিarr_2[i]নন-জিরো হয়,count = min(count, arr_1[i]/arr_2[i])(প্রতিটি অক্ষরstr_1-এ শুধু একবার ব্যবহার করেstr_2-এর অক্ষর পূরণ)।- শেষে
count-এ মিলে যাওয়া অক্ষরের ন্যূনতম অনুপাত থাকবে। উদাহরণ: aaabbbb (a=3,b=4) এবং abb (a=1,b=2) → মিনিমাম ১। countরিটার্ন করুন।
উদাহরণ
#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
