Підрахувати підрядки з рівною кількістю 0, 1 і 2  


Рівень складності Жорсткий
Часто запитують у Citrix FreeCharge Goldman Sachs Номери OYO Times Інтернет Twilio
Мішанина рядок

У задачі “Підрахувати підрядки з рівною кількістю 0, 1 і 2” вказано, що вам дано a рядок що має лише 0, 1 і 2. Постановка задачі вимагає з’ясувати кількість підрядків, які містять рівне число лише 0, 1 і 2.

Приклад  

Підрахувати підрядки з рівною кількістю 0, 1 і 2Pin

str= “01200”
2

Пояснення

Двома підрядками, які мають однакову кількість 0, 1 і 2, є (012) та (120).

str= “10201012”
4

Пояснення

Чотири підрядки, які мають однакову кількість 0, 1 і 2, є (102) та (201), (012) та (201012).

Алгоритм  

  1. Заявіть a карта.
  2. Ініціалізуйте пару до 0 і помістіть її на карту за допомогою 1.
  3. Установка нульовий рахунок, один рахунок, два рахунки, і вихід в 0.
  4. Цикл від i = 0 до i
    1. Перевірте для кожного символу поточного підрядка, чи дорівнює він 0, 1 і 2. Потім відповідно оновіть відлік.
    2. Обчисліть різниці пар.
    3. Перевірте, чи різниці немає на карті, додайте 0 до виводу.
    4. В іншому випадку додайте значення temp в карту у вихідні дані.
    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.

На даний момент ми знайшли всі наші можливі підрядки, це спосіб, яким ми отримуємо рівне число 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

Код Java для підрахунку підрядків з рівною кількістю 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

Аналіз складності  

Складність часу

О (п)  де "N" - кількість елементів у масиві. Оскільки ми використовували HashMap, усі вставки, видалення та пошук вимагають лише O (1) часу на операцію.

Складність простору

О (п)  де "N" - кількість елементів у масиві.