Подсчет подстрок с равным количеством нулей, единиц и двоек


Сложный уровень Жесткий
Часто спрашивают в Citrix Свободный заряд Goldman Sachs OYO Номера Таймс Интернет Twilio
Hash строка

Задача «Подсчитать подстроки с равным количеством нулей, единиц и двоек» утверждает, что вам дается строка который имеет только 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 на карте. Рассчитайте разницу между нулевой счет и один счети нулевой счет и два счета. Мы будем хранить значение в паре и эту пару на карте. Если разница пары уже существует на карте, просто получите / извлеките значение текущей пары из карты. Затем добавьте это к выводу. Если разницы еще нет на карте. Затем добавьте к выходу 0. Нам также необходимо вставить пару разностей в карту и увеличить ее частоту, если она уже существует на карте. В противном случае сохраните новую запись для пары разностей со значением 1 в карте.

Рассмотрим для этого пример:

Пример

Строка = «01200»

Мы уже инициализировали пару до 0 и вставили пару в качестве ключа и 1 в качестве значения в карту. Мы получим первый символ, например 0. Итак, мы вычислим пару разностей и получим (1,1). Кроме того, это потому, что мы увеличили количество нулей. Мы посчитаем разницу и получим результат. После получения значения текущего значения карты и добавления 0 к выходным данным, потому что эта пара новая. Мы просто вставим пару в карту. Текущий выход равен 0.

Мы выберем следующего символа - 1. Теперь мы увеличим счетчик одного. Тогда мы получим разницу 0,1. Поскольку эта пара также новая, мы добавим ее на карту, и результат останется прежним.

Затем мы получим 2 в качестве входных данных, мы получим пару как 0, 0, потому что теперь счетчик цифр равен 1. Мы сохраним это тоже на карте и на этот раз обновим вывод, потому что 0,0 мы уже инициализировали в карте так что теперь на выходе будет 1.

Далее мы получаем как 0, теперь нулевой счет равен двум. Мы получаем 1,1, так как это уже есть на карте. Затем мы обновим вывод и вставим его на карту со значением 2.

На данный момент мы нашли все возможные подстроки, таким образом мы не получаем равенства нулей, единиц и двоек.

Код:

Код 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

Код Java для подсчета подстрок с равным количеством нулей, единиц и двоек

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

Анализ сложности

Сложность времени

О (п)  в котором «Н» - количество элементов в массиве. Поскольку мы использовали HashMap, для всех операций вставки, удаления и поиска требуется всего O (1) раз на операцию.

Космическая сложность

О (п)  в котором «Н» это количество элементов в массиве.