0s, 1s ਅਤੇ 2s ਦੇ ਬਰਾਬਰ ਗਿਣਤੀ ਵਾਲੇ ਸਬਸਟ੍ਰਿੰਗਜ਼ ਦੀ ਗਿਣਤੀ ਕਰੋ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਸਿਟ੍ਰਿਕਸ ਫ੍ਰੀਚਾਰਜ ਗੋਲਡਮੈਨ ਸਾਕਸ ਓਏ ਕਮਰੇ ਟਾਈਮਜ਼ ਇੰਟਰਨੈੱਟ Twilio
ਹੈਸ਼ ਸਤਰ

"0s, 1s ਅਤੇ 2s ਦੀ ਬਰਾਬਰ ਗਿਣਤੀ ਦੇ ਨਾਲ ਗਿਣਨ ਵਾਲੀਆਂ ਸਬਸਟ੍ਰਿੰਗਜ਼" ਸਮੱਸਿਆ ਦੱਸਦੀ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਏ ਸਤਰ ਉਸ ਕੋਲ ਸਿਰਫ 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. ਸੈੱਟ ਕਰੋ ਜ਼ੀਰੋਕਾਉਂਟ, onecount, ਦੋਹਰਾ ਅਤੇ ਆਉਟਪੁੱਟ 0 ਤੱਕ
  4. I = 0 ਤੋਂ i ਤੱਕ ਲੂਪ
    1. ਮੌਜੂਦਾ ਸਬਸਟ੍ਰਿੰਗ ਦੇ ਹਰੇਕ ਅੱਖਰ ਦੀ ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਇਹ 0, 1 ਅਤੇ 2 ਹੈ. ਫਿਰ ਗਿਣਤੀ ਨੂੰ ਇਸ ਅਨੁਸਾਰ ਅਪਡੇਟ ਕਰੋ.
    2. ਜੋੜਾ ਦੇ ਅੰਤਰ ਦੀ ਗਣਨਾ ਕਰੋ.
    3. ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਨਕਸ਼ੇ ਵਿੱਚ ਅੰਤਰ ਮੌਜੂਦ ਨਹੀਂ ਹੈ, ਫਿਰ, ਆਉਟਪੁੱਟ ਵਿੱਚ 0 ਸ਼ਾਮਲ ਕਰੋ.
    4. ਹੋਰ, ਆਉਟਪੁੱਟ ਵਿੱਚ ਨਕਸ਼ੇ ਦਾ ਅਸਥਾਈ ਮੁੱਲ ਸ਼ਾਮਲ ਕਰੋ.
    5. ਨਕਸ਼ੇ ਵਿੱਚ ਅਸਥਾਈ ਸ਼ਾਮਲ ਕਰੋ.
  5. ਵਾਪਸੀ ਆਉਟਪੁੱਟ.

ਕਥਾ

ਸਾਨੂੰ ਇਕ ਸਤਰ ਦਿੱਤੀ ਗਈ ਹੈ ਜਿਸ ਵਿਚ ਸਿਰਫ 0, 1, ਅਤੇ 2 ਹਨ. ਸਾਡਾ ਕੰਮ ਸਬਸਟ੍ਰਿੰਗਸ ਦੀ ਕੁੱਲ ਸੰਖਿਆ ਦਾ ਪਤਾ ਲਗਾਉਣਾ ਹੈ ਜਿਸ ਦੇ ਬਰਾਬਰ ਨੰਬਰ 0, 1 ਅਤੇ 2 ਹਨ. ਇਸਦੇ ਲਈ, ਅਸੀਂ ਇਸਤੇਮਾਲ ਕਰ ਰਹੇ ਹਾਂ ਹੈਸ਼ਿੰਗ. ਡਿਫੌਲਟ ਰੂਪ ਵਿੱਚ, ਇੱਕ ਜੋੜੀ ਨੂੰ ਕੁੰਜੀ ਦੇ ਰੂਪ ਵਿੱਚ (0, 0) ਅਤੇ ਇਸਦੇ ਮੁੱਲ 1 ਦੇ ਤੌਰ ਤੇ ਅਰੰਭ ਕਰੋ. ਵਿਚਕਾਰ ਅੰਤਰ ਦੀ ਗਣਨਾ ਕਰੋ ਜ਼ੀਰੋਕਾਉਂਟ ਅਤੇ onecountਹੈ, ਅਤੇ ਜ਼ੀਰੋਕਾਉਂਟ ਅਤੇ twocount. ਅਸੀਂ ਇਕ ਜੋੜੀ ਵਿਚ ਮੁੱਲ ਨੂੰ ਸਟੋਰ ਕਰਾਂਗੇ ਅਤੇ ਉਹ ਜੋੜਾ ਨਕਸ਼ੇ ਵਿਚ. ਜੇ ਨਕਸ਼ੇ ਵਿਚ ਪਹਿਲਾਂ ਹੀ ਇਕ ਜੋੜਾ ਦਾ ਅੰਤਰ ਮੌਜੂਦ ਹੈ, ਤਾਂ ਬੱਸ ਨਕਸ਼ੇ ਤੋਂ ਮੌਜੂਦਾ ਜੋੜੀ ਦਾ ਮੁੱਲ ਪ੍ਰਾਪਤ / ਪ੍ਰਾਪਤ ਕਰੋ. ਫਿਰ ਇਸਨੂੰ ਆਉਟਪੁੱਟ ਵਿੱਚ ਸ਼ਾਮਲ ਕਰੋ. ਜੇ ਫਰਕ ਪਹਿਲਾਂ ਹੀ ਨਕਸ਼ੇ ਵਿੱਚ ਮੌਜੂਦ ਨਹੀਂ ਹੈ. ਫਿਰ ਆਉਟਪੁੱਟ ਵਿੱਚ 0 ਸ਼ਾਮਲ ਕਰੋ. ਸਾਨੂੰ ਨਕਸ਼ੇ ਵਿਚ ਅੰਤਰ ਅੰਤਰ ਜੋੜਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਅਤੇ ਇਸ ਦੀ ਬਾਰੰਬਾਰਤਾ ਵਧਾਉਣੀ ਚਾਹੀਦੀ ਹੈ ਜੇ ਇਹ ਪਹਿਲਾਂ ਹੀ ਨਕਸ਼ੇ ਵਿਚ ਮੌਜੂਦ ਹੈ. ਨਹੀਂ ਤਾਂ ਫਰਕ ਦੀ ਜੋੜੀ ਲਈ ਇੱਕ ਨਵੀਂ ਐਂਟਰੀ ਨੂੰ ਨਕਸ਼ੇ ਵਿਚ ਇਕ ਮੁੱਲ ਦੇ ਤੌਰ ਤੇ 1 ਨਾਲ ਸਟੋਰ ਕਰੋ.

ਆਓ ਇਸਦੀ ਇੱਕ ਉਦਾਹਰਣ ਤੇ ਵਿਚਾਰ ਕਰੀਏ:

ਉਦਾਹਰਨ

ਸਤਰ = "01200"

ਅਸੀਂ ਪਹਿਲਾਂ ਹੀ ਜੋੜੀ ਨੂੰ 0 ਤੋਂ ਸ਼ੁਰੂ ਕਰ ਚੁੱਕੇ ਹਾਂ ਅਤੇ ਨਕਸ਼ੇ ਵਿਚ ਜੋੜੀ ਨੂੰ ਕੁੰਜੀ ਦੇ ਰੂਪ ਵਿਚ ਅਤੇ 1 ਮੁੱਲ ਦੇ ਤੌਰ ਤੇ ਪਾਓ. ਅਸੀਂ ਪਹਿਲੇ ਪਾਤਰ ਨੂੰ 0. ਵਰਗੇ ਪ੍ਰਾਪਤ ਕਰਾਂਗੇ. ਇਸ ਲਈ ਅਸੀਂ ਅੰਤਰ ਜੋੜੀ ਦੀ ਗਣਨਾ ਕਰਾਂਗੇ ਅਤੇ ਪ੍ਰਾਪਤ ਕਰਾਂਗੇ (1,1). ਅਤੇ, ਇਹ ਇਸ ਲਈ ਹੈ ਕਿਉਂਕਿ ਅਸੀਂ ਜ਼ੀਰੋ ਦੀ ਗਿਣਤੀ ਵਧਾ ਦਿੱਤੀ ਹੈ. ਇਸ ਲਈ ਅਸੀਂ ਅੰਤਰ ਦੀ ਗਣਨਾ ਕਰਾਂਗੇ ਅਤੇ ਨਤੀਜਾ ਪ੍ਰਾਪਤ ਕਰਾਂਗੇ. ਨਕਸ਼ੇ ਦੇ ਮੌਜੂਦਾ ਮੁੱਲ ਦੀ ਕੀਮਤ ਪ੍ਰਾਪਤ ਕਰਨ ਅਤੇ ਆਉਟਪੁੱਟ ਵਿੱਚ 0 ਜੋੜਨ ਤੋਂ ਬਾਅਦ, ਕਿਉਂਕਿ ਇਹ ਜੋੜਾ ਨਵਾਂ ਹੈ. ਅਸੀਂ ਜੋੜੀ ਨੂੰ ਨਕਸ਼ੇ ਵਿੱਚ ਪਾਵਾਂਗੇ. ਮੌਜੂਦਾ ਆਉਟਪੁੱਟ 0 ਹੈ.

ਅਸੀਂ ਅਗਲੇ ਚਰਿੱਤਰ ਲਈ ਜਾਵਾਂਗੇ ਜੋ ਕਿ 1 ਹੈ. ਹੁਣ ਅਸੀਂ ਇਕ ਦੀ ਗਿਣਤੀ ਵਧਾਵਾਂਗੇ. ਤਦ ਸਾਨੂੰ ਅੰਤਰ 0,1 ਦੇ ਰੂਪ ਵਿੱਚ ਪ੍ਰਾਪਤ ਹੋਣਗੇ. ਕਿਉਂਕਿ ਇਹ ਜੋੜਾ ਵੀ ਨਵਾਂ ਹੈ, ਇਸ ਲਈ ਅਸੀਂ ਇਸਨੂੰ ਨਕਸ਼ੇ ਵਿੱਚ ਸ਼ਾਮਲ ਕਰਾਂਗੇ ਅਤੇ ਆਉਟਪੁੱਟ ਅਜੇ ਵੀ ਉਹੀ ਰਹਿੰਦੀ ਹੈ.

ਫਿਰ ਸਾਨੂੰ ਇੱਕ ਇੰਪੁੱਟ ਦੇ ਰੂਪ ਵਿੱਚ 2 ਮਿਲਦਾ ਹੈ ਜੋੜੀ ਨੂੰ 0, 0 ਦੇ ਰੂਪ ਵਿੱਚ ਪ੍ਰਾਪਤ ਕਰਾਂਗੇ ਕਿਉਂਕਿ ਸਾਰੇ ਅੰਕ ਦੀ ਗਿਣਤੀ ਹੁਣ 1 ਹੈ. ਅਸੀਂ ਇਸਨੂੰ ਵੀ ਨਕਸ਼ੇ ਵਿੱਚ ਸਟੋਰ ਕਰਾਂਗੇ ਅਤੇ ਇਸ ਵਾਰ ਅਪਡੇਟ ਆਉਟਪੁੱਟ ਕਿਉਂਕਿ 0,0 ਅਸੀਂ ਪਹਿਲਾਂ ਹੀ ਇੱਕ ਨਕਸ਼ੇ ਵਿੱਚ ਅਰੰਭ ਕਰ ਚੁੱਕੇ ਹਾਂ. ਆਉਟਪੁਟ ਹੁਣ 1 ਹੈ.

ਅੱਗੇ, ਅਸੀਂ 0 ਵਾਂਗ ਪ੍ਰਾਪਤ ਕਰਦੇ ਹਾਂ, ਹੁਣ ਜ਼ੀਰੋਕਾਉਂਟ ਦੋ ਹਨ. ਸਾਨੂੰ 1,1 ਮਿਲਦਾ ਹੈ ਕਿਉਂਕਿ ਇਹ ਪਹਿਲਾਂ ਹੀ ਨਕਸ਼ੇ ਵਿੱਚ ਹੈ. ਫੇਰ ਅਸੀ ਆਉਟਪੁਟ ਨੂੰ ਅਪਡੇਟ ਕਰਾਂਗੇ ਅਤੇ ਇਸਨੂੰ ਵੈਲਯੂ 2 ਨਾਲ ਮੈਪ ਵਿੱਚ ਪਾਵਾਂਗੇ.

ਇਸ ਬਿੰਦੂ ਤੇ ਸਾਨੂੰ ਆਪਣੀਆਂ ਸਾਰੀਆਂ ਸੰਭਵ ਸਬਸਟ੍ਰਿੰਗਸ ਮਿਲੀਆਂ ਹਨ, ਇਹ ਉਹ ਤਰੀਕਾ ਹੈ ਜਿਸ ਨਾਲ ਸਾਨੂੰ 0 ਦੇ 1, 2 ਅਤੇ XNUMX ਦੇ ਬਰਾਬਰ ਨੰਬਰ ਮਿਲਦੇ ਹਨ.

ਕੋਡ

0+, 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

ਬਰਾਬਰ ਨੰਬਰ 0, 1 ਅਤੇ 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)  ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ. ਕਿਉਂਕਿ ਅਸੀਂ ਹੈਸ਼ਮੈਪ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਹੈ, ਸਾਰੀ ਸੰਮਿਲਨ, ਹਟਾਉਣ ਅਤੇ ਖੋਜ ਲਈ ਸਿਰਫ ਓ (1) ਸਮੇਂ ਪ੍ਰਤੀ ਕਾਰਜ ਦੀ ਜ਼ਰੂਰਤ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਹੇ (n)  ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ.