Максимизируйте непересекающиеся подстроки, разделив строку на группы с K или (K + 1) 1s

Для заданной двоичной строки S длины N и целого числа K задача состоит в том, чтобы найти максимальное количество непересекающихся подстрок, которые можно получить, разделив ее в соответствии со следующими условиями:

• Каждая подстрока строки содержит K или K+1 число 1 .
• Не более чем K последовательных подстрок могут содержать одинаковое количество единиц.

Примечание. Если строка не содержит K или K + 1 единиц, просто игнорируйте эту подстроку.

Примеры:

 Input: S = “110101000010011011011011000100000”, K = 2
Output: 6
Explanation: The given string can be split into – [110], [10100], [00100110], [110], [110], [11000100000] so the answer is 6.

Input: S = “0000010001001100000110101100110000”, K = 2
Output: 5
Explanation: The given string can be split into – [000001000100], [1100000], [1101], [0110], [0110000] so the answer is 5. 

Input: S = “11111111111”, K = 4
Output: 2
Explanation: The string can be split into [1111], [1111] and 
The remaining string can be neglected because it does not contain K number of 1s.

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

To maximize the count of substrings splitting such that as many substring have count of ‘1’ as K. 
As it is not possible to split string having same number of ‘1’ successively more than K times, so after splitting K substrings with count of ‘1’ as K, split a substring with count of ‘1’ as K + 1.

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

• Итерировать строку от i = 0 до N-1 :
  • Продолжайте добавлять символы в текущую подстроку, пока количество единиц не станет K .
  • Если в последовательных K подстроках уже было одинаковое количество подстрок, перейдите вперед и добавьте еще одну 1 в текущую подстроку и начните новую подстроку.
  • Увеличить счетчик количества подстрок.
  • Если невозможно иметь K единиц, тогда игнорируйте эту подстроку.
• Возвращает окончательное количество подстрок.

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

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