0s, 1s અને 2s ની સમાન સંખ્યાવાળા સબસ્ટ્રિંગ્સની ગણતરી કરો  


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે સિટ્રીક્સ ફ્રીચાર્જ ગોલ્ડમૅન સૅશ ઓયો ઓરડાઓ ટાઇમ્સ ઇન્ટરનેટ 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. ઘોષણા કરો એ નકશો.
  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 તરીકે જોડી પ્રારંભ કરો. વચ્ચેના તફાવતની ગણતરી કરો ઝીરોકાઉન્ટ અને ગણતરી, અને ઝીરોકાઉન્ટ અને બે ગણું. અમે જોડીમાં કિંમત અને તે જોડીને નકશામાં સંગ્રહિત કરીશું. જો જોડીનો તફાવત નકશામાં પહેલેથી જ અસ્તિત્વમાં છે, તો પછી નકશામાંથી વર્તમાન જોડીનું મૂલ્ય ખાલી મેળવો / પ્રાપ્ત કરો. પછી તેને આઉટપુટમાં ઉમેરો. જો તફાવત પહેલાથી નકશામાં હાજર નથી. પછી આઉટપુટમાં 0 ઉમેરો. આપણે નકશામાં તફાવતની જોડવાની પણ જરૂર છે અને જો તે નકશામાં પહેલાથી અસ્તિત્વમાં છે તો તેની આવર્તન વધારવી જોઈએ. બાકી નકશામાં મૂલ્ય તરીકે તફાવત જોડી માટે નવી એન્ટ્રી સ્ટોર કરો.

આ પણ જુઓ
શ્રેણીના ગુમ તત્વો શોધો

ચાલો આપણે તેના માટે એક ઉદાહરણ ધ્યાનમાં લઈએ:

ઉદાહરણ

શબ્દમાળા = "01200"

આપણે જોડીને 0 થી પહેલેથી જ પ્રારંભ કરી દીધી છે અને નકશામાં કી તરીકે 1 અને મૂલ્યની 0 જોડી છે. આપણે 1,1. જેવા પ્રથમ પાત્રને પ્રાપ્ત કરીશું, તેથી આપણે તફાવત જોડીની ગણતરી કરીશું અને (0) મેળવીશું. ઉપરાંત, આ કારણ છે કે આપણે શૂન્યની ગણતરી વધારી છે. તો આપણે તફાવતની ગણતરી કરીશું અને પરિણામ મેળવીશું. નકશાના વર્તમાન મૂલ્યનું મૂલ્ય મેળવ્યા પછી અને આઉટપુટમાં 0 ઉમેર્યા પછી, કારણ કે આ જોડી નવી છે. અમે જોડીને ફક્ત નકશામાં દાખલ કરીશું. વર્તમાન આઉટપુટ XNUMX છે.

આપણે હવે પછીના પાત્ર માટે જઈશું. 1. હવે આપણે કોઈની ગણતરી વધારીશું. પછી આપણને 0,1 તરીકે તફાવતો મળશે. કેમ કે આ જોડી પણ નવી છે, તેથી અમે તેને નકશામાં ઉમેરીશું અને આઉટપુટ હજી પણ તેવું જ રહેશે.

પછી આપણને ઇનપુટ તરીકે 2 મળે છે, આપણે જોડી 0, 0 તરીકે મેળવીશું કારણ કે અંકોની ગણતરી હવે 1 છે. આપણે તે પણ નકશામાં સંગ્રહ કરીશું અને આ સમય અપડેટ આઉટપુટ કારણ કે 0,0 આપણે નકશામાં પહેલેથી જ પ્રારંભ કરી દીધું છે. તેથી આઉટપુટ હવે 1 છે.

આગળ, આપણે 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 અને 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

જટિલતા વિશ્લેષણ  

સમય જટિલતા

ઓ (એન)  જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. કારણ કે અમે હેશમેપનો ઉપયોગ કર્યો છે, તેથી બધા દાખલ, કાtionી નાખવા અને શોધવામાં ઓપરેશન દીઠ ફક્ત ઓ (1) સમયની જરૂર છે.

અવકાશ જટિલતા

ઓ (એન)  જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.

આ પણ જુઓ
દ્વિસંગી વૃક્ષમાં નિવેશ