0 টি, 1 এবং 2 এর সমান সংখ্যার সহ সাবস্ট্রিংগুলি গণনা করুন


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় Citrix ফ্রিচার্জ গোল্ডম্যান শ্যাস ওয় রুমগুলি টাইমস ইন্টারনেট 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) এবং (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 এর সমান নম্বর রয়েছে এটির জন্য, আমরা ব্যবহার করতে যাচ্ছি হ্যাশ। ডিফল্টরূপে মানচিত্রের মান হিসাবে 0 (0, 1) এবং এর মান XNUMX হিসাবে একটি জুটি সূচনা করুন। এর মধ্যে পার্থক্য গণনা করুন জিরোকাউন্ট এবং গণনা, এবং জিরোকাউন্ট এবং দ্বিগুণ। আমরা মানচিত্রটিতে একটি জোড়ায় এবং সেই জুটিটি সংরক্ষণ করব। যদি কোনও জোড়ার পার্থক্য মানচিত্রে ইতিমধ্যে বিদ্যমান থাকে তবে কেবল মানচিত্র থেকে বর্তমান জোড়ার মানটি / পুনরুদ্ধার করুন। তারপরে আউটপুটটিতে এটি যুক্ত করুন। পার্থক্যটি যদি মানচিত্রে ইতিমধ্যে উপস্থিত না থাকে। তারপরে আউটপুটটিতে 0 যুক্ত করুন। আমাদের মানচিত্রে পার্থক্যটির জোড় inোকানো এবং মানচিত্রে এটি ইতিমধ্যে বিদ্যমান থাকলে এর ফ্রিকোয়েন্সি বাড়ানো দরকার। অন্য মানচিত্রে মান হিসাবে 1 দিয়ে পার্থক্যটির জন্য একটি নতুন এন্ট্রি সঞ্চয় করুন।

আসুন আমরা এর জন্য একটি উদাহরণ বিবেচনা করি:

উদাহরণ

স্ট্রিং = "01200"

আমরা ইতিমধ্যে জোড়টিকে 0 তে আরম্ভ করেছি এবং মান হিসাবে জোড় 1 টি এবং 0 টি মান হিসাবে জোড় .োকালাম। আমরা 1,1 এর মতো প্রথম চরিত্রটি পুনরুদ্ধার করব So এছাড়াও, কারণ আমরা শূন্যের সংখ্যা বাড়িয়েছি। সুতরাং আমরা পার্থক্য গণনা এবং ফলাফল পাবেন। মানচিত্রের বর্তমান মানের মান পাওয়ার পরে এবং আউটপুটটিতে 0 যুক্ত করার পরে, কারণ এই জুটিটি নতুন। আমরা জোড়টিকে মানচিত্রে সন্নিবেশ করব। বর্তমান আউটপুট 0 হয়।

আমরা পরবর্তী চরিত্রের জন্য যাব যে 1 হবে। এখন আমরা কারওর সংখ্যা বাড়িয়ে দেব। তারপরে আমরা 0,1 হিসাবে পার্থক্যগুলি পেয়ে যাব। যেহেতু এই জুটিটিও নতুন, তাই আমরা এটি মানচিত্রে যুক্ত করব এবং আউটপুটটি এখনও একই থাকবে।

তারপরে আমরা ইনপুট হিসাবে ২ টি পাই আমরা জোড়াকে 2, 0 হিসাবে পেয়ে যাব কারণ অঙ্কের সমস্ত গণনা এখন ১ টি that সুতরাং আউটপুট এখন 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

0 টি, 1 এবং 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

জটিলতা বিশ্লেষণ

সময় জটিলতা

উপর)  কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। যেহেতু আমরা হ্যাশম্যাপ ব্যবহার করেছি, সমস্ত সন্নিবেশ, মুছে ফেলা এবং অনুসন্ধানের জন্য প্রতিটি ক্রিয়াকলাপে কেবল ও (1) সময় প্রয়োজন।

স্পেস জটিলতা ity

উপর)  কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।