0s ، 1s اور 2s کی مساوی تعداد کے ساتھ سبسٹرنگز گنیں


مشکل سطح ہارڈ
اکثر پوچھا جاتا ہے Citrix کی فریچارج گولڈمین سیکس OYO کمرے ٹائمز انٹرنیٹ Twilio
ہیش سلک

مسئلہ "0s ، 1s اور 2s کی مساوی تعداد کے ساتھ سب گنٹر شمار کریں" یہ بتاتا ہے کہ آپ کو a سٹرنگ جس میں صرف 0 ، 1 ، اور 2 ہیں۔ مسئلے کے بیان میں سب سبسٹنگز کی تعداد معلوم کرنے کے لئے کہا گیا ہے جس میں صرف 0 ، 1 ، اور 2 کے برابر نمبر ہیں۔

مثال کے طور پر

0s ، 1s اور 2s کی مساوی تعداد کے ساتھ سبسٹرنگز گنیں

str= “01200”
2

وضاحت

دو سبسٹرنگز ، جن کی تعداد 0 ، 1 ، اور 2 ہیں (012) اور (120)۔

str= “10201012”
4

وضاحت

چار سبسٹرنگز ، جن کی 0 ، 1 ، اور 2 کی برابر تعداد ہے (102) اور (201) ، (012) اور (201012)۔

الگورتھم

  1. اعلان a نقشہ.
  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 کے برابر نمبر والے سبسٹرنگز کی کل تعداد کا پتہ لگائیں۔ اس کے لئے ، ہم استعمال کرنے جا رہے ہیں ہیکنگ. (0 ، 0) کے ساتھ ایک جوڑی کو بطور کلید اور اس کی قدر 1 کے ساتھ نقشہ میں ، ابتدائی طور پر شروع کریں۔ کے درمیان فرق کا حساب لگائیں زیروکاؤنٹ اور اونکاؤنٹ، اور زیروکاؤنٹ اور twocount. ہم نقشہ میں ایک جوڑی میں قیمت جوڑیں گے اور وہ جوڑی۔ اگر نقشہ میں پہلے سے ہی کسی جوڑے کا فرق موجود ہے تو پھر نقشہ سے موجودہ جوڑی کی قدر کو آسانی سے / حاصل کریں۔ پھر اسے آؤٹ پٹ میں شامل کریں۔ اگر فرق نقشہ میں پہلے سے موجود نہیں ہے۔ پھر آؤٹ پٹ میں 0 کا اضافہ کریں۔ ہمیں نقشہ میں بھی جوڑی ڈالنے کی ضرورت ہے اور اگر نقشہ میں پہلے سے موجود ہے تو اس کی تعدد میں اضافہ کرنا ہے۔ دوسری صورت میں نقشہ میں قدر کی حیثیت سے فرق کے جوڑے کیلئے ایک نئی اندراج ذخیرہ کریں۔

آئیے ہم اس کی ایک مثال پر غور کریں:

مثال کے طور پر

تار = "01200"

ہم نے جوڑی کو پہلے ہی 0 میں شروع کیا ہے اور نقشہ میں جوڑی بطور کلیدی اور 1 داخل کی ہے۔ ہم 0 جیسے پہلے کردار کو بازیافت کریں گے۔ لہذا ہم فرق کی جوڑی کا حساب لگائیں گے اور (1,1،0) حاصل کریں گے۔ نیز ، اس کی وجہ یہ ہے کہ ہم نے صفر کی گنتی میں اضافہ کیا ہے۔ تو ہم فرق کا حساب لیں گے اور اس کا نتیجہ حاصل کریں گے۔ نقشہ کی موجودہ قیمت کی قیمت حاصل کرنے اور آؤٹ پٹ میں 0 کا اضافہ کرنے کے بعد ، کیونکہ یہ جوڑا نیا ہے۔ ہم جوڑے کو صرف نقشہ میں داخل کریں گے۔ موجودہ پیداوار XNUMX ہے۔

ہم اگلے کردار کے لئے جائیں گے جو 1 ہے۔ اب ہم کسی کی گنتی میں اضافہ کریں گے۔ پھر ہمیں 0,1،XNUMX کی طرح فرق ملے گا۔ چونکہ یہ جوڑا بھی نیا ہے ، لہذا ہم اسے نقشہ میں شامل کریں گے اور آؤٹ پٹ اب بھی ایک جیسی ہے۔

پھر ہمیں ان پٹ کے طور پر 2 ملیں گے ، ہم جوڑا 0 ، 0 کے طور پر حاصل کریں گے کیونکہ ہندسے کی تمام گنتی اب 1 ہے۔ ہم اسے بھی نقشہ میں اسٹور کریں گے اور اس بار اپ ڈیٹ آؤٹ پٹ کیونکہ 0,0،1 ہم نے پہلے ہی نقشے میں ابتدا کی ہے۔ لہذا پیداوار اب XNUMX ہے۔

اگلا ، ہم 0 کی طرح ملتے ہیں ، اب زیروکاونٹ دو ہے۔ ہمیں 1,1،2 ملتا ہے کیونکہ یہ نقشہ میں پہلے ہی موجود ہے۔ تب ہم آؤٹ پٹ کو اپ ڈیٹ کریں گے اور اسے ویلیو XNUMX کے ساتھ نقشہ میں داخل کریں گے۔

اس مقام پر ہمیں اپنی تمام ممکنہ سبسٹرنگز مل گئیں ، یہی طریقہ ہے کہ ہمیں 0 ، 1 اور 2 کے برابر نمبر ملتے ہیں۔

ضابطے

0s ، 1s اور 2s کی مساوی تعداد کے ساتھ سبسٹرنگوں کو گننے کے لئے C ++ کوڈ

#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 اور 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

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

اے (ن)  کہاں "این" صف میں عناصر کی تعداد ہے۔ چونکہ ہم نے ہش میپ کا استعمال کیا ہے ، لہذا سارے اضافے ، حذف کرنے اور تلاش کرنے کے لئے فی آپریشن میں صرف O (1) وقت درکار ہوتا ہے۔

خلائی پیچیدگی

اے (ن)  کہاں "این" صف میں عناصر کی تعداد ہے۔