Подсчет непересекающихся подмассивов размера K с равными альтернативными элементами

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

Примеры:

Input: arr[] = {2, 4, 2, 7}, K = 3
Output: 1
Explanation:  Given subarray {2, 4, 2} is a valid array because the elements in even position(index no.0 and 2) are equal. Hence the count of the subarrays with size K = 3 is 1.

Input: arr[] =  {5, 2, 5, 2, 3, 9, 7, 9, 7}, K = 4
Output: 2
Explanation:  Subarray {5, 2, 5, 2} and {9, 7, 9, 7} are valid subarrays because the elements in even position(index no.0 and 2) and odd positions(index no.1 and 3) are equal.  Hence the count of the subarrays with size K = 4 is 2.

Подход: реализуйте приведенную ниже идею, чтобы решить проблему.

Initially find all the non-overlapping subarrays where  alternate elements are equal. Comparing the lengths of each such subarray with K, we can find out how many valid subarrays of size K can be extracted from each of those.

Для реализации идеи выполните следующие шаги:

• Инициализируйте t = 2 в начале и c = 0, чтобы поддерживать количество подмассивов.
• Перебрать массив из индекса 2.
• Всякий раз, когда мы находим arr[i] = arr[i-2], увеличиваем t на 1.
• Когда t станет равным K , увеличьте c на 1 и сбросьте t = 0 .
• Если длина данного массива arr[] меньше 2, см. значение K и соответственно верните вывод.
• После итерации по массиву верните c в качестве подмассивов счетчика.

Ниже приведена реализация описанного выше подхода.

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

Статьи по Теме:

• Введение в массивы - учебные пособия по структурам данных и алгоритмам