Количество подмассивов длины K, содержащих только 1 в заданной двоичной строке

Для заданной двоичной строки str задача состоит в том, чтобы найти количество подмассивов длины K , содержащих только единицы.

Примеры:

Input: str = “0101000”, K=1
Output: 2
Explanation: 0101000 -> There are 2 subarrays with 1 ones

Input: str = “11111001”, K=3
Output: 3

Подход : Задача может быть решена путем отслеживания размеров группы последовательных . Как только мы получим groupSize , мы можем сделать вывод, что количество возможных подмассивов длины k и все 1 равны groupSize – k + 1 .

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

• Перебрать двоичную строку с самого начала
• Увеличивайте счетчик, если встречается 1 и в точке, где приходит 0 .
• Сохраните текущий счетчик , чтобы получить groupSize последовательных единиц, и повторно инициализируйте счетчик равным 0.
• Добавьте количество возможных подмассивов размера k в этот groupSize, используя отношение groupSize – k + 1
• Возвращает окончательную сумму count.

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

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