एक स्ट्रिंग से दूसरी स्ट्रिंग बनाने के लिए प्रत्येक अक्षर का अधिकतम एक बार उपयोग करके बनने वाली स्ट्रिंग्स की गणना - C++

समस्या विवरण

हमें दो स्ट्रिंग्स str1 और str2 दी गई हैं। लक्ष्य यह गणना करना है कि str1 के अक्षरों का उपयोग करके (प्रत्येक अक्षर अधिकतम एक बार) str2 की कितनी पूर्ण प्रतियाँ बनाई जा सकती हैं।

उदाहरण

इनपुट: str_1 = "technical learning", str_2 = "learning"

आउटपुट: 1

व्याख्या: "learning" के सभी अक्षर "technical learning" में ठीक एक बार आते हैं।

इनपुट: str_1 = "ellohsehelloabcoelhl", str_2 = "hello"

आउटपुट: 3

व्याख्या: "hello" बनाने के लिए आवश्यक अक्षर str_1 में 3 बार पूरे होते हैं।

दृष्टिकोण

दोनों स्ट्रिंग्स में प्रत्येक अक्षर की आवृत्ति गिनें। str2 के प्रत्येक अक्षर के लिए, str1 में उसकी आवृत्ति को str2 में उसकी आवृत्ति से विभाजित करें। सभी अक्षरों के लिए इन भागफलों का न्यूनतम मान उत्तर होगा।

एल्गोरिदम

1. दोनों स्ट्रिंग्स और उनकी लंबाई लें
2. प्रारंभिक count = INT_MAX
3. आकार 26 का ऐरे arr[] बनाएँ और 0 से आरंभ करें
4. str_1 को पार करें: arr[str_1[i] - 'a']++
5. str_2 को पार करें: count = min(count, arr[str_2[i] - ''])
6. count लौटाएँ

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";
    string str_2 = "learning";
    cout << "Count: " << atmost_once(str_1, str_1.length(), str_2, str_2.length());
    return 0;
}

आउटपुट

Count: 1