Перевернуть все 0 в заданных двоичных строках K раз с разными соседями
Учитывая двоичную строку 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 по диапазону [0, N – 1], используя переменную j , и выполните следующие шаги:
- После выполнения вышеуказанных шагов выведите строку S в качестве результирующей модифицированной строки.
Ниже приведена реализация вышеуказанного подхода:
Output : 11111011
Временная сложность: O(N*K)
Вспомогательное пространство: O(N)