Максимальная длина последовательных единиц или нулей после переключения не более чем K символов

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

Примеры :

Input: S = “1001”, K = 1
Output: 3
Explanation:
Flip the K(= 1) characters at index 3 of the string modifies the string S to “1000”. Now the maximum length of consecutive 0s is 3, which is the required result.

Input: S = “11011011”, K = 3
Output: 8

Подход: Данная проблема может быть решена с использованием подхода двух указателей и подхода скользящего окна. Выполните шаги, чтобы решить данную проблему:

• Инициализируйте функцию, скажем, maxLength(S, N, ch, K) , которая находит максимальную длину символов ch после перестановки не более чем K символов, используя следующие шаги:
  1. Инициализируйте переменную, скажем, cnt , которая хранит количество символов ch в окне.
  2. Инициализируйте переменную, скажем, левую , которая хранит начало результирующего окна.
  3. Инициализируйте переменную, скажем, an , которая сохраняет результирующую длину последовательных K символов как ch после не более чем K переворотов.
  4. Перейдите строку S , используя переменную right , и выполните следующие шаги:
     • Если значение S[right] равно ch , то увеличьте значение cnt на 1 .
     • Повторяйте до тех пор, пока значение cnt не станет больше K , затем увеличьте левый указатель и уменьшите значение cnt на 1 .
     • Обновите значение ans до максимума ans and (right – left + 1) .
• После выполнения вышеуказанных шагов выведите в качестве результата максимальное значение, возвращаемое maxLength(S, N, '0', K) и maxLength(S, N, '1', K) .

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

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