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

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

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

Примеры:

Input: S = “00010110 “, K = 3
Output: 3
Explanation:
Below are the operations performed:

  1. Consider the substring S[0, 2] which is of size K(= 3) and flipping those characters modifies the string to “11110110”.
  2. Consider the substring S[4, 6] which is of size K(= 3) and flipping those characters modifies the string to “11111000”.
  3. Consider the substring S[5, 7] which is of size K(= 3) and flipping those characters modifies the string to “11111111”.

After the above operations, all the 0s are converted to 1s, and the minimum number of operations required is 3.

Input: S = “01010”, K = 4
Output: -1

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

  • Инициализируйте переменную, скажем, minOperations как 0 , которая хранит счетчик минимального количества необходимых операций.
  • Пройдите строку S , используя переменную i , и если символы S[i] равны «0», а значение (i + K) не более K , затем переверните все символы подстроки S[i, i + K] и увеличьте значение minOperations на 1 .
  • После вышеуказанных операций пройдитесь по строке S и, если существует какой-либо символ «0», выведите «-1» и прервите цикл.
  • Если все символы строки S равны 1 , то выведите minOperations как результирующее минимальное количество операций.

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


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

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