Подсчет подмассивов, содержащих не менее X различных элементов, которые встречаются ровно Y раз

Даны три целых числа N , X , Y и массив arr[] размера N , задача состоит в том, чтобы найти количество подмассивов, содержащих не менее X различных элементов, которые встречаются только Y раз.

Пример:

Input: N = 9, X = 2, Y = 2, arr[] = {2, 1, 2, 5, 3, 1, 3, 2, 5}
Output:10
Explanation:
Subarrays with at least X distinct elements occurring exactly Y times are: 
{2, 1, 2, 5, 3, 1}, {2, 1, 2, 5, 3, 1, 3}, {2, 1, 2, 5, 3, 1, 3, 2}, {2, 1, 2, 5, 3, 1, 3, 2, 5},  
{1, 2, 5, 3, 1, 3}, {1, 2, 5, 3, 1, 3, 2}, {1, 2, 5, 3, 1, 3, 2, 5}, {2, 5, 3, 1, 3, 2},  
{2, 5, 3, 1, 3, 2, 5}, {5, 3, 1, 3, 2, 5}

Input: N = 3, X = 1, Y = 2, arr[] = {1, 3, 5}
Output: 0
Explanation: No element is occurring twice in the given array

Наивный подход: идея состоит в том, чтобы сгенерировать все возможные подмассивы заданного массива и пройтись по сгенерированным подмассивам, чтобы найти частоту всех отдельных элементов. Затем проверьте, есть ли по крайней мере X различных элементов, которые встречаются только Y раз в подмассиве. Если найдено, увеличьте результат и верните окончательный результат.

Временная сложность: O(N ³ )
Вспомогательное пространство: O(N)

Эффективный подход: проблема также может быть решена эффективным способом, основанным на следующей идее:

Keep track of the frequency of elements while generating the subarray and count of unique elements with exactly Y occurrences in that subarray with the help of hashing. In this way, there is no need to build all the subarrays and check them afterward.

Выполните следующие шаги, чтобы реализовать вышеуказанную идею:

• Итерация от i = 0 до N – 1 :
  • Объявите хэш-карту (скажем, cntFreq ) для хранения частоты отдельных элементов в подмассиве.
  • Инициализируйте переменную (скажем, cntDistinct ) для хранения количества различных элементов, которые встречаются ровно Y раз в подмассиве.
  • Выполните итерацию, используя вложенный цикл от j = i до N , чтобы рассмотреть все подмассивы:
    • Увеличьте частоту arr[j] .
    • Если частота равна Y , увеличьте cntDistinct .
    • Если частота превышает Y и становится Y+1 , уменьшается cntDistinct ,
  • Если в подмассиве есть как минимум X различных элементов, удовлетворяющих условию, увеличьте количество подмассивов, удовлетворяющих условию.
• Наконец, верните количество подмассивов.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N ² )
Вспомогательное пространство: O(N)