गुब्बारे लेटेकोड समाधान की अधिकतम संख्या


कठिनाई स्तर आसान
में अक्सर पूछा टेस्ला Wayfair
hashing तार

समस्या का विवरण

इस समस्या में, हमें निचले अक्षरों वाले अंग्रेजी अक्षरों वाले अक्षरों की एक स्ट्रिंग दी जाती है। हमें यह खोजने की जरूरत है कि शब्द के कितने उदाहरण हैं ”गुब्बारा"क्या हम दिए गए स्ट्रिंग के वर्णों का उपयोग कर सकते हैं।

उदाहरण

String = "banooll"
1

व्याख्या:

गुब्बारे लेटेकोड समाधान की अधिकतम संख्या

String = baqwweeeertylln
0

व्याख्या: जैसे कि स्ट्रिंग में कोई 'ओ' नहीं है, हम "गुब्बारे" का एक भी उदाहरण नहीं बना सकते हैं। तो, हम 0 प्रिंट करते हैं।

दृष्टिकोण

यह स्पष्ट है कि हमें स्ट्रिंग में अक्षरों की आवृत्ति को जानना होगा जो शब्द "गुब्बारा" बनाता है। यही है, हमारे लिए केवल पत्र 'बी', 'ए', 'एल', 'ओ' और 'एन' की आवृत्तियों को बचाना महत्वपूर्ण है क्योंकि वे स्ट्रिंग "बैलून" का निर्माण करते हैं। फिर, हम संभव शब्द के उदाहरणों की संख्या तय करने के लिए न्यूनतम गणना वाले अक्षर पा सकते हैं। इसका एक विशिष्ट उदाहरण है हैशिंग उनकी आवृत्तियों के साथ वर्ण। ध्यान दें कि हमें यह विचार करने की आवश्यकता है कि 'l' और 'o' अक्षरों की केवल आधी आवृत्तियों का उपयोग एक शब्द बनाने के लिए किया जा सकता है। इस मामले को सामान्य बनाने के लिए, हम इन दो अक्षरों की आवृत्ति को पहले से आधा कर देते हैं।

कलन विधि

  1. प्रारंभिक 5 पूर्णांक: बी, ए, एल, ओ, और n के रूप में उनकी संबंधित आवृत्तियों को संग्रहीत करने के लिए 0
  2. हर किरदार के लिए 'chrस्ट्रिंग में:
    • अगर 'chr'उपर्युक्त वर्णों में से कोई भी है, इसकी आवृत्ति बढ़ाना
  3. फूट डालो l और o 2 द्वारा
  4. के बीच न्यूनतम वापसी बी, ए, एल, ओ, और n
  5. परिणाम प्रिंट करें

गुब्बारे लेटेकोड समाधान की अधिकतम संख्या का कार्यान्वयन

C ++ प्रोग्राम

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

int maxNumberOfBalloons(string text)
{
    int b = 0 , a = 0 , l = 0 , o = 0 , n = 0;
    for(char &chr : text)
    {
        switch(chr)
        {
            case 'b' : b++;
                break;
            case 'a' : a++;
                break;
            case 'l' : l++;
                break;
            case 'o' : o++;
                break;
            case 'n' : n++;
                break;
        }
    }

    l /= 2;
    o /= 2;
    return min({b , a , l , o , n});
}

int main()
{
    string text = "blloona";
    cout << maxNumberOfBalloons(text) << '\n';
    return 0;
}

जावा प्रोग्राम

import java.lang.*;

class max_balloons
{
    public static void main(String args[])
    {
        String text = "blloona";
        System.out.println(maxNumberOfBalloons(text));
    }

    static int maxNumberOfBalloons(String text)
    {
        int b = 0 , a = 0 , l = 0 ,  o = 0 , n = 0;
        char chr;
        for(int i = 0 ; i < text.length() ; i++)
        {
            chr = text.charAt(i);
            switch(chr)
            {
                case 'b' : b++;
                case 'a' : a++;
                case 'l' : l++;
                case 'o' : o++;
                case 'n' : n++;
                default: ;
            }
        }

        l /= 2;
        o /= 2;

        return Math.min(b , Math.min(a , Math.min(l, Math.min(o , n))));
    }
}
1

गुब्बारे लेटेकोड समाधान की अधिकतम संख्या की जटिलता विश्लेषण

समय जटिलता

पर) जैसा कि हम कुछ वर्णों की आवृत्तियों को संग्रहीत करने के लिए स्ट्रिंग को एक बार पार करते हैं। यहाँ, N = सरणी का आकार।

अंतरिक्ष जटिलता 

ओ (1) जैसा कि हम इनपुट के बावजूद निरंतर मेमोरी स्पेस का उपयोग करते हैं। हम केवल उनकी आवृत्तियों की गणना के लिए कुछ चर संग्रहित करते हैं।