0, 1 आणि 2 एस समान संख्येसह सबस्ट्रिंग मोजा


अडचण पातळी हार्ड
वारंवार विचारले सिट्रिक्स फ्रीचार्ज गोल्डमन Sachs ओयओ रूम्स टाइम्स इंटरनेट Twilio
हॅश अक्षरमाळा

“0s, 1s आणि 2s समान संख्येसह गणना सबस्ट्रिंग्स” ही समस्या सांगते की आपल्याला ए स्ट्रिंग त्याकडे केवळ 0, 1 आणि 2 आहेत. समस्या विधानात केवळ 0, 1 आणि 2 इतकीच संख्या असलेल्या सबस्ट्रिंगची संख्या शोधण्यास सांगितले जाते.

उदाहरण

0, 1 आणि 2 एस समान संख्येसह सबस्ट्रिंग मोजा

str= “01200”
2

स्पष्टीकरण

दोन सबस्ट्रिंग्ज, ज्यांची 0, 1 आणि 2 ची समान संख्या आहे (012) आणि (120).

str= “10201012”
4

स्पष्टीकरण

चार सबस्ट्रिंग्ज, ज्यांची 0, 1 आणि 2 ची समान संख्या आहे (102) आणि (२०१०), (201) आणि (012).

अल्गोरिदम

  1. घोषित ए नकाशा.
  2. 0 ची जोडी आरंभ करा आणि 1 सह नकाशामध्ये ठेवा.
  3. सेट करा शून्य, onecount, दुहेरी आणि आउटपुट 0 पर्यंत.
  4. I = 0 ते i मधील पळवाट
    1. सद्यस्ट्र्रिंगची प्रत्येक अक्षरे 0, 1 आणि 2 आहे का ते तपासा. त्यानंतर त्यानुसार गणना अद्यतनित करा.
    2. जोडीतील फरकांची गणना करा.
    3. नकाशामध्ये फरक नसल्याचे तपासा, तर आउटपुटमध्ये 0 जोडा.
    4. अन्यथा, आउटपुटमध्ये टेम्पचे नकाशाचे मूल्य जोडा.
    5. नकाशावर अस्थायी जोडा.
  5. रिटर्न आउटपुट

स्पष्टीकरण

आम्हाला फक्त 0, 1, आणि 2 असलेली एक स्ट्रिंग दिली आहे. आमचे कार्य 0, 1 आणि 2 च्या समान संख्या असलेल्या सबस्ट्रिंगची एकूण संख्या शोधणे आहे. यासाठी आम्ही वापरणार आहोत हॅशिंग. की (0, 0) सह जोडी आरंभ करा आणि डीफॉल्टनुसार नकाशामध्ये त्याचे मूल्य 1 असा करा. यातील फरक मोजा शून्य आणि onecountआणि शून्य आणि दुहेरी. आम्ही जोडीमध्ये मूल्य आणि ते जोडी नकाशामध्ये साठवत आहोत. नकाशामध्ये आधीपासूनच जोडीचा फरक अस्तित्वात असल्यास, नकाशावरून फक्त वर्तमान जोडीचे मूल्य मिळवा / मिळवा. नंतर ते आउटपुटमध्ये जोडा. फरक आधीपासूनच नकाशामध्ये नसल्यास. नंतर आउटपुटमध्ये 0 जोडा. आम्हाला नकाशामध्ये फरक जोड घालण्याची आणि ते आधीपासूनच नकाशामध्ये अस्तित्त्वात असल्यास त्याची वारंवारता वाढविणे देखील आवश्यक आहे. अन्यथा नकाशामध्ये मूल्य म्हणून भिन्न फर जोडीसाठी नवीन प्रविष्टी संचयित करा.

चला त्याचं उदाहरण घेऊ:

उदाहरण

स्ट्रिंग = “01200”

आम्ही आधीपासून 0 ची जोडी आरंभ केली आहे आणि नकाशात मूल्य म्हणून 1 आणि की म्हणून जोडली आहे. आपण ० सारखे पहिले वर्ण मिळवू. म्हणून आम्ही भिन्न जोडीची गणना करू आणि (१,१) मिळवू. हे देखील आहे कारण आपण शून्य ची संख्या वाढविली आहे. तर आम्ही फरक मोजू आणि तो निकाल मिळवू. नकाशाच्या वर्तमान मूल्याचे मूल्य प्राप्त झाल्यानंतर आणि आउटपुटमध्ये 0 जोडल्यामुळे, ही जोडी नवीन आहे. आम्ही जोडी फक्त नकाशामध्ये घालू. सध्याचे आउटपुट 1,1 आहे.

आपण पुढच्या चार पात्रासाठी जाऊ. आता आपण एखाद्याची संख्या वाढवू. नंतर आपल्याला 1 म्हणून फरक मिळेल. ही जोडी देखील नवीन असल्याने आम्ही ती नकाशात जोडू आणि आऊटपुट अजूनही तशीच राहील.

नंतर आपल्याला इनपुट म्हणून २ मिळेल, जोडी 2, 0 म्हणून मिळतील कारण सर्व अंकांची गणना आता 0 आहे. आम्ही ती देखील नकाशामध्ये संचयित करू आणि या वेळेचे अद्यतन आउटपुट कारण 1 आम्ही आधीच नकाशात आरंभ केले आहे. आऊटपुट आता 0,0 आहे.

पुढे आपण 0 सारखे, आता झिरोकाउंट दोन आहोत. हे आधीपासूनच नकाशामध्ये असल्याने आम्हाला 1,1 मिळेल. नंतर आउटपुट अपडेट करू आणि व्हॅल्यू 2 सह नकाशामध्ये समाविष्ट करू.

याक्षणी आम्हाला आमची सर्व संभाव्य सबस्ट्रिंग्ज सापडली आहेत, अशाप्रकारे आपल्याला 0, 1 आणि 2 ची समान संख्या मिळेल.

कोड

0, 1 से आणि 2 एस समान संख्येसह सबस्ट्रिंग मोजण्यासाठी सी ++ कोड

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

struct hash_pair { 
    template <class T1, class T2> 
    size_t operator()(const pair<T1, T2>& p) const
    { 
        auto hash1 = hash<T1>{}(p.first); 
        auto hash2 = hash<T2>{}(p.second); 
        return hash1 ^ hash2; 
    } 
}; 

int getSubString(string str)
{
    int n = str.length();
    unordered_map< pair<int, int>, int, hash_pair > MAP;
    MAP[make_pair(0, 0)] = 1;
    int zerocount = 0, onecount = 0, twocount = 0;
    int output = 0;
    for (int i = 0; i < n; ++i)
    {
        if (str[i] == '0')
            zerocount++;
        else if (str[i] == '1')
            onecount++;
        else
            twocount++;
        pair<int, int> x = make_pair(zerocount - onecount,zerocount - twocount);
        output = output + MAP[x];
        MAP[x]++;
    }
    return output;
}
int main()
{
    string str = "10201012";
    cout << getSubString(str) << endl;
    return 0;
}
4

0s, 1s आणि 2 एस समान संख्येसह सबस्ट्रिंग मोजण्यासाठी जावा कोड

import java.util.HashMap;
class Pair
{
    int first, second;
    Pair(int x, int y)
    {
        this.first=x;
        this.second=y;
    }
}
class SubstringCount
{
    public static int getSubString012(String str1)
    {
        int n = str1.length();

        HashMap< String, Integer > MAP=new HashMap<>();



        MAP.put("0:0", 1);

        int zerocount = 0, onecount = 0, twocount = 0;

        int output = 0;
        for (int i = 0; i < n; ++i)
        {
            if (str1.charAt(i)=='0')
                zerocount++;
            else if (str1.charAt(i) == '1')
                onecount++;
            else
                twocount++;

            Pair pair = new Pair(zerocount - onecount, zerocount - twocount);

            String str=pair.first+":"+pair.second;

            if(!MAP.containsKey(str))
                output = output + 0;
            else
                output = output + MAP.get(str);

            if(MAP.containsKey(str))
                MAP.put(str, MAP.get(str)+1);
            else
                MAP.put(str, 1);
        }

        return output;
    }
    public static void main(String [] args)
    {
        String str = "10201012";
        System.out.println(getSubString012(str));
    }
}
4

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

O (n)  जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. आम्ही हॅशमॅप वापरल्यामुळे सर्व समाविष्ट करणे, हटविणे आणि शोधण्यासाठी प्रत्येक ऑपरेशनमध्ये फक्त ओ (1) वेळ आवश्यक आहे.

स्पेस कॉम्प्लेक्सिटी

O (n)  जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.