Преобразуйте данную двоичную строку S во все 1, изменив все 0 на 1 в диапазоне [i+1, i+K], если S[i] равно 1

Для заданной двоичной строки S размера N и числа K задача состоит в том, чтобы выяснить, можно ли заменить все «0» на « 1» за любое количество операций. В одной операции, если S[i] изначально равно '1' , то все '0 ' в диапазоне [i+1, i+K] могут быть изменены на '1' для 0≤i<NK .

Примеры:

Input: S=”100100″, N=6, K=2
Output: YES
Explanation: S[0] can be used to change S[1] and S[2] into 1s
S[3] can be used to change S[4] and S[5] into 1s

Input: S=”110000″, N=6, K=2
Output: NO

Наивный подход: самый простой подход состоит в том, чтобы пройти по строке в обратном порядке и, если встречается «0» , проверить, находится ли позиция ближайшей «1» слева более чем на K индексов. Если верно, то выведите «NO» .

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

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

• Инициализируйте флаг двух переменных и подсчитайте их как 1 и 0 соответственно, чтобы сохранить результат и подсчитать количество ' 0' , которые были изменены последним вхождением ' 1' .
• Инициализировать пустой стек st .
• Перейдите строку S и сделайте следующее:
  • Если стек пуст:
    • Если текущий элемент равен '0' , измените флаг на 0 и сломайте, так как этот ' 0' не может быть изменен на '1' .
    • В противном случае обновите count до 0 и нажмите 1 до st .
  • В противном случае:
    • Если текущий элемент равен «0», выполните следующие действия:
      • Увеличить счетчик на 1.
      • Если count становится равным K , извлеките стек st и обновите count до 0
    • В противном случае обновите счетчик до 0 .
• Если значение флага равно 1 , выведите «YES» , иначе в качестве результата выведите «NO» .

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

Временная сложность: O(N)
Вспомогательный пробел: O(1), поскольку в любой момент времени в стеке присутствует не более одного символа.