Перевернуть все 0 в заданных двоичных строках K раз с разными соседями

Опубликовано: 22 Сентября, 2022

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

Note: For the character 0 present at 0th index then it will change to 1 only when 1st index character is 1 and if the last index character is 0 then it changes to ‘1’ if the second last index character is ‘1’.

Примеры:

Input: S = “01001”, K = 2
Output: 11111
Explanation:
Below are the operation performed K(= 2) number of times:|
Operation 1: After flipping the string at indices 0, 2, 3, the string modifies to “11111”.
Operation 2: There is no such possible flipping for the modified string S = “11111”.
After the above operations, the modified string is “11111”.

Input: S = “10010001”, K = 3
Output: 11111011

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

  • Переберите диапазон [0, K – 1], используя переменную i , и выполните следующие шаги:
    • Пройдите заданную строку S по диапазону [0, N – 1], используя переменную j , и выполните следующие шаги:
      • Если символ в 0 индексе равен 0 , то замените это значение первым значение индекса.
      • В противном случае, если в последнем индексе присутствует символ 0 , замените это значение предпоследним символом индекса .
      • В противном случае преобразуйте все 0 в 1 , если соседние символы различны.
    • После вышеуказанных шагов, если строка осталась прежней до модификации, выйти из цикла.
  • После выполнения вышеуказанных шагов выведите строку S в качестве результирующей модифицированной строки.

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

Output : 11111011

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ