0, 1s और 2s के बराबर संख्या के साथ सबस्ट्रिंग की गणना करें


कठिनाई स्तर कठिन
में अक्सर पूछा Citrix स्वतंत्र प्रभार गोल्डमैन सैक्स ओयो कमरे टाइम्स इंटरनेट Twilio
हैश तार

समस्या "0, 1s और 2s के बराबर संख्या वाली सबस्ट्रिंग्स की गणना" बताती है कि आपको a स्ट्रिंग जिसमें 0, 1 और 2 ही हैं। समस्या कथन उन सबस्ट्रेट्स की संख्या का पता लगाने के लिए कहता है जिनमें 0, 1, और 2 के बराबर संख्याएँ होती हैं।

उदाहरण

0, 1s और 2s के बराबर संख्या के साथ सबस्ट्रिंग की गणना करें

str= “01200”
2

व्याख्या

दो सबस्ट्रिंग, जिनकी संख्या 0, 1 और 2 के बराबर है (012) और (120) हैं।

str= “10201012”
4

व्याख्या

चार सब्सट्रिंग्स, जिनकी संख्या 0, 1, और 2 के बराबर है (102) और (201), (012) और (201012)।

कलन विधि

  1. डिक्लेयर ए नक्शा.
  2. एक जोड़ी को 0 पर शुरू करें और इसे 1 के साथ मैप में डालें।
  3. सेट शून्य, आगे बढ़ना, गोधूलि, और उत्पादन 0 लिए.
  4. लूप से i = 0 से i
    1. वर्तमान के प्रत्येक वर्ण की जाँच करें कि क्या यह 0, 1 और 2 है।
    2. जोड़ी के अंतर की गणना करें।
    3. जांचें कि क्या अंतर मानचित्र में मौजूद नहीं है, फिर, आउटपुट में 0 जोड़ें।
    4. और, आउटपुट में टेम्प के मानचित्र का मान जोड़ें।
    5. नक्शे में अस्थायी जोड़ें।
  5. वापसी आउटपुट।

व्याख्या

हमें एक स्ट्रिंग दी गई है जिसमें 0, 1 और 2 ही हैं। हमारा कार्य उन कुलियों की कुल संख्या का पता लगाना है जिनकी संख्या 0, 1 और 2 के बराबर है। इसके लिए, हम उपयोग करने जा रहे हैं hashing। कुंजी के रूप में (0, 0) के साथ एक जोड़ी को शुरू करें और डिफ़ॉल्ट रूप से मानचित्र में 1 के रूप में इसका मूल्य। के बीच अंतर की गणना करें शून्य और आगे बढ़ना, तथा शून्य और दो टूक। हम एक जोड़ी में मान जमा करेंगे और उस जोड़ी को मानचित्र में लाएंगे। यदि मानचित्र में पहले से ही एक जोड़ी का अंतर मौजूद है, तो बस मानचित्र से वर्तमान जोड़ी के मूल्य को प्राप्त / पुनः प्राप्त करें। फिर उस आउटपुट में जोड़ें। यदि अंतर पहले से ही नक्शे में मौजूद नहीं है। फिर आउटपुट में 0 जोड़ें। हमें मानचित्र में अंतर जोड़ी सम्मिलित करने और इसकी आवृत्ति बढ़ाने की आवश्यकता है यदि यह पहले से ही नक्शे में मौजूद है। 1 नक्शे में मूल्य के रूप में XNUMX के साथ अंतर जोड़ी के लिए एक नई प्रविष्टि स्टोर करें।

आइए हम इसके लिए एक उदाहरण पर विचार करें:

उदाहरण

स्ट्रिंग = "01200"

हमने पहले से ही जोड़ी को 0 से जोड़ा है और जोड़ी को मानचित्र में मान के रूप में कुंजी और 1 के रूप में सम्मिलित किया है। हम 0. जैसे पहले वर्ण को पुनः प्राप्त करेंगे, इसलिए हम अंतर जोड़ी की गणना करेंगे और प्राप्त करेंगे (1,1)। इसके अलावा, यह इसलिए है क्योंकि हमने शून्य की गिनती में वृद्धि की है। तो हम अंतर की गणना करेंगे और उस परिणाम को प्राप्त करेंगे। मानचित्र के वर्तमान मूल्य को प्राप्त करने और आउटपुट में 0 जोड़ने के बाद, क्योंकि यह जोड़ी नई है। हम जोड़ी को मानचित्र में सम्मिलित करेंगे। वर्तमान उत्पादन 0 है।

हम अगले चरित्र के लिए जाएंगे। फिर हमें 1 के रूप में अंतर मिलेगा। चूंकि यह जोड़ी भी नई है, इसलिए हम इसे मैप में जोड़ देंगे और आउटपुट अभी भी वही है।

फिर हम एक इनपुट के रूप में 2 प्राप्त करते हैं, हम जोड़े को 0, 0 के रूप में प्राप्त करेंगे क्योंकि सभी अंकों की गिनती अब 1 है। हम इसे मानचित्र में भी संग्रहीत करेंगे और इस बार आउटपुट को अपडेट करेंगे क्योंकि 0,0 हमने पहले ही एक नक्शे में आरंभीकृत कर लिया है। इसलिए आउटपुट अब 1 है।

इसके बाद, हम 0 की तरह हो जाते हैं, अब शून्य दो है। हमें 1,1 मिलता है क्योंकि यह पहले से ही नक्शे में है। फिर हम आउटपुट को अपडेट करेंगे और इसे मान 2 के साथ मैप में डालें।

इस बिंदु पर हमने अपने सभी संभव पदार्थों को पा लिया है, यही तरीका है कि हमें 0, 1 और 2 के बराबर संख्या नहीं मिलती है।

कोड

C ++ कोड को 0, 1s और 2s के बराबर संख्या वाले सबस्ट्रिंग की गणना करने के लिए

#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

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

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

जटिलता विश्लेषण

समय जटिलता

पर)  जहां "N" सरणी में तत्वों की संख्या है। चूँकि हमने HashMap, प्रविष्टि, विलोपन, और खोज का उपयोग किया है, इसलिए प्रति ऑपरेशन केवल O (1) समय की आवश्यकता होती है।

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

पर)  जहां "N" सरणी में तत्वों की संख्या है।