C++-এ একটি স্ট্রিং থেকে অন্য স্ট্রিং তৈরির সম্ভাব্য সংখ্যা গণনা (প্রতিটি ক্যারেক্টার একবার ব্যবহার)

আমাদের দুটি স্ট্রিং str1 এবং str2 দেওয়া আছে। লক্ষ্য হল str1-এর ক্যারেক্টারগুলো ব্যবহার করে (প্রতিটি ক্যারেক্টার শুধু একবার ব্যবহার করে) str2 কতবার তৈরি করা যায় তা বের করা।

উদাহরণ

ইনপুট: str_1 = "technical learning", str_2 = "learning"

আউটপুট: ১

ব্যাখ্যা: str_2 এর সব ক্যারেক্টার str_1-এ একবারের মতো পাওয়া যায়।

ইনপুট: str_1 = "ellohsehelloabcoelhl", str_2 = "hello"

আউটপুট: ৩

ব্যাখ্যা: str_1-এ 'h','e','l','l','o' ক্যারেক্টারগুলো যথেষ্ট আছে ৩টি "hello" বানাতে।

অ্যালগরিদম

1. দুটি স্ট্রিং এবং তাদের দৈর্ঘ্য ইনপুট নিন।
2. ২৬ আকারের ফ্রিকোয়েন্সি অ্যারে arr[26] তৈরি করুন এবং ০ দিয়ে ইনিশিয়ালাইজ করুন।
3. str_1 ট্রাভার্স করে প্রতিটি ক্যারেক্টারের ফ্রিকোয়েন্সি বড়ান: arr[str_1[i] - 'a']++।
4. count = INT_MAX দিয়ে শুরু করুন।
5. str_2 ট্রাভার্স করে: count = min(count, arr[str_2[i] - 'a'])।
6. count ফেরত দিন — এটি str_2 কতবার তৈরি করা যাবে তা নির্দেশ করে।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

int atmost_once(string str_1, int len_str1, string str_2, int len_str2) {
    int count = INT_MAX;
    int arr[26] = {0};
    
    for (int i = 0; i < len_str1; i++) {
        if (str_1[i] >= 'a' && str_1[i] <= 'z')
            arr[str_1[i] - 'a']++;
    }
    
    for (int i = 0; i < len_str2; i++) {
        if (str_2[i] >= 'a' && str_2[i] <= 'z')
            count = min(count, arr[str_2[i] - 'a']);
    }
    return count;
}

int main() {
    string str_1 = "technical learning";
    int length_str1 = str_1.length();
    string str_2 = "learning";
    int length_str2 = str_2.length();
    cout << "Count of strings that can be formed from another string using each character at-most once are: " 
         << atmost_once(str_1, length_str1, str_2, length_str2);
    return 0;
}

আউটপুট

Count of strings that can be formed from another string using each character at-most once are: 1