0 സെ, 1 സെ, 2 സെ എന്നിവയുടെ തുല്യ സംഖ്യയുള്ള സബ്സ്ട്രിംഗുകളുടെ എണ്ണം  


വൈഷമ്യ നില ഹാർഡ്
പതിവായി ചോദിക്കുന്നു ക്സെൻ ഫ്രീചാർജ് ഗോൾഡ്മാൻ സാക്സ് OYO മുറികൾ ടൈംസ് ഇന്റർനെറ്റ് ട്വിలియో
ഹാഷ് സ്ട്രിംഗ്

“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. ഗണം സീറോക ount ണ്ട്, ഒറ്റത്തവണ, ഇരട്ട കണക്ക്, ഒപ്പം ഔട്ട്പുട്ട് 0 ലേക്ക്.
  4. I = 0 മുതൽ i വരെ ലൂപ്പ് ചെയ്യുക
    1. നിലവിലെ സബ്‌സ്ട്രിംഗിന്റെ ഓരോ പ്രതീകവും 0, 1, 2 എന്നിവയാണോയെന്ന് പരിശോധിക്കുക. അതിനുശേഷം എണ്ണം അപ്‌ഡേറ്റുചെയ്യുക.
    2. ജോഡിയുടെ വ്യത്യാസങ്ങൾ കണക്കാക്കുക.
    3. മാപ്പിൽ വ്യത്യാസം ഇല്ലേ എന്ന് പരിശോധിക്കുക, തുടർന്ന് 0 ട്ട്‌പുട്ടിലേക്ക് XNUMX ചേർക്കുക.
    4. അല്ലെങ്കിൽ, .ട്ട്‌പുട്ടിലേക്ക് ടെമ്പിന്റെ മാപ്പിന്റെ മൂല്യം ചേർക്കുക.
    5. മാപ്പിലേക്ക് താൽക്കാലികം ചേർക്കുക.
  5. Return ട്ട്‌പുട്ട് നൽകുന്നു.

വിശദീകരണം

0, 1, 2 എന്നിവ മാത്രമുള്ള ഒരു സ്ട്രിംഗ് ഞങ്ങൾക്ക് നൽകിയിരിക്കുന്നു. 0, 1, 2 എന്നിവയ്ക്ക് തുല്യമായ സബ്‌സ്ട്രിംഗുകളുടെ ആകെ എണ്ണം കണ്ടെത്തുക എന്നതാണ് ഞങ്ങളുടെ ചുമതല. ഇതിനായി ഞങ്ങൾ ഉപയോഗിക്കാൻ പോകുന്നു ഹാഷിംഗ്. (0, 0) കീയായി ഒരു ജോഡിയും അതിന്റെ മൂല്യം മാപ്പിലേക്ക് 1 ആയി സ്ഥിരസ്ഥിതിയായി സമാരംഭിക്കുക. തമ്മിലുള്ള വ്യത്യാസം കണക്കാക്കുക സീറോക ount ണ്ട് ഒപ്പം ഒറ്റത്തവണ, ഒപ്പം സീറോക ount ണ്ട് ഒപ്പം ഇരട്ട കണക്ക്. ഞങ്ങൾ മൂല്യം ഒരു ജോഡിയിലും ആ ജോഡി മാപ്പിലും സംഭരിക്കും. ഒരു ജോഡിയുടെ വ്യത്യാസം ഇതിനകം മാപ്പിൽ നിലവിലുണ്ടെങ്കിൽ, മാപ്പിൽ നിന്ന് നിലവിലെ ജോഡിയുടെ മൂല്യം നേടുക / വീണ്ടെടുക്കുക. അത് the ട്ട്‌പുട്ടിലേക്ക് ചേർക്കുക. മാപ്പിൽ ഇതിനകം വ്യത്യാസം ഇല്ലെങ്കിൽ. Out ട്ട്‌പുട്ടിലേക്ക് 0 ചേർക്കുക. മാപ്പിൽ വ്യത്യാസ ജോഡി ഉൾപ്പെടുത്തുകയും മാപ്പിൽ ഇതിനകം നിലവിലുണ്ടെങ്കിൽ അതിന്റെ ആവൃത്തി വർദ്ധിപ്പിക്കുകയും വേണം. മാപ്പിലേക്ക് ഒരു മൂല്യമായി 1 ഉള്ള വ്യത്യാസ ജോഡിക്ക് പുതിയ എൻ‌ട്രി സംഭരിക്കുക.

ഇതും കാണുക
ഒരു ശ്രേണിയുടെ നഷ്‌ടമായ ഘടകങ്ങൾ കണ്ടെത്തുക

അതിനുള്ള ഒരു ഉദാഹരണം നമുക്ക് പരിഗണിക്കാം:

ഉദാഹരണം

സ്ട്രിംഗ് = “01200”

ഞങ്ങൾ ഇതിനകം ജോഡിയെ 0 ലേക്ക് സമാരംഭിക്കുകയും ജോഡി കീയായി 1 ഉം മാപ്പിലേക്ക് 0 മൂല്യമായി ചേർക്കുകയും ചെയ്തു. 1,1 പോലുള്ള ആദ്യത്തെ പ്രതീകം ഞങ്ങൾ വീണ്ടെടുക്കും. അതിനാൽ ഞങ്ങൾ വ്യത്യാസ ജോഡി കണക്കാക്കി (0) ലഭിക്കും. കൂടാതെ, പൂജ്യത്തിന്റെ എണ്ണം ഞങ്ങൾ വർദ്ധിപ്പിച്ചതിനാലാണിത്. അതിനാൽ ഞങ്ങൾ വ്യത്യാസം കണക്കാക്കുകയും ആ ഫലം ​​നേടുകയും ചെയ്യും. മാപ്പിന്റെ നിലവിലെ മൂല്യത്തിന്റെ മൂല്യം നേടി output ട്ട്‌പുട്ടിൽ 0 ചേർത്തതിന് ശേഷം, കാരണം ഈ ജോഡി പുതിയതാണ്. ഞങ്ങൾ ജോഡി മാപ്പിൽ തിരുകും. നിലവിലെ output ട്ട്‌പുട്ട് XNUMX ആണ്.

1 എന്ന അടുത്ത പ്രതീകത്തിനായി ഞങ്ങൾ പോകും. ഇപ്പോൾ നമ്മൾ ഒരാളുടെ എണ്ണം വർദ്ധിപ്പിക്കും. അപ്പോൾ നമുക്ക് 0,1 ആയി വ്യത്യാസങ്ങൾ ലഭിക്കും. ഈ ജോഡിയും പുതിയതായതിനാൽ ഞങ്ങൾ അത് മാപ്പിലേക്ക് ചേർക്കും, output ട്ട്‌പുട്ട് ഇപ്പോഴും അങ്ങനെ തന്നെ തുടരും.

അപ്പോൾ നമുക്ക് 2 ഇൻപുട്ടായി ലഭിക്കും, കാരണം ജോഡിയെ 0, 0 ആയി ലഭിക്കും, കാരണം അക്കത്തിന്റെ എല്ലാ എണ്ണവും ഇപ്പോൾ 1 ആണ്. അതും ഞങ്ങൾ മാപ്പിൽ സംഭരിക്കും, കൂടാതെ ഇത്തവണ അപ്‌ഡേറ്റ് output ട്ട്‌പുട്ട് 0,0 ഞങ്ങൾ ഇതിനകം ഒരു മാപ്പിൽ സമാരംഭിച്ചു അതിനാൽ 1 ട്ട്‌പുട്ട് ഇപ്പോൾ XNUMX ആണ്.

അടുത്തതായി, നമുക്ക് 0 പോലെ ലഭിക്കും, ഇപ്പോൾ സീറോക ount ണ്ട് രണ്ടാണ്. ഇത് ഇതിനകം തന്നെ മാപ്പിൽ ഉള്ളതിനാൽ ഞങ്ങൾക്ക് 1,1 ലഭിക്കുന്നു. തുടർന്ന് ഞങ്ങൾ output ട്ട്‌പുട്ട് അപ്‌ഡേറ്റ് ചെയ്യുകയും മൂല്യം 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

സങ്കീർണ്ണത വിശകലനം  

സമയ സങ്കീർണ്ണത

O (n)  എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഞങ്ങൾ ഹാഷ്‌മാപ്പ് ഉപയോഗിച്ചതിനാൽ, ഉൾപ്പെടുത്തൽ, ഇല്ലാതാക്കൽ, തിരയൽ എന്നിവയ്‌ക്ക് ഓരോ പ്രവർത്തനത്തിനും O (1) സമയം മാത്രമേ ആവശ്യമുള്ളൂ.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n)  എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം.