Лексикографически наименьшая двоичная строка, образованная путем перестановки битов по индексам, не делящимся на K1 или K2, так что количество единиц всегда больше, чем нулей слева.

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

Для заданной двоичной строки S (индексация на основе 1) размера N и двух положительных целых чисел K1 и K2 задача состоит в том, чтобы найти лексикографически наименьшую строку, перевернув символы в индексах, которые не делятся ни на K1 , ни на K2 , так что количество 1 с до тех пор, пока каждый возможный индекс всегда больше, чем количество 0 с. Если такую строку сформировать невозможно, выведите «-1» .

Примеры:

Input: K1 = 4, K2 = 6, S = “0000”
Output: 1110
Explanation:
Since the index 4 is divisible by K1(= 4). So without flipping that index the string modifies to  “1110”, which is lexicographically smallest among all possible combinations of flips.

Input: K1 = 2, K2 = 4, S = “11000100”
Output: 11100110

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

  • Инициализируйте две переменные, скажем, c1 и c0 , чтобы хранить количество 1 и 0 соответственно.
  • Инициализируйте вектор, скажем, pos[] , который хранит позиции всех нулей , которые не делятся на K1 или K2 .
  • Пройдите по заданной строке S и выполните следующие шаги:
    • Если символ равен 0 , увеличьте значение c0 . В противном случае увеличьте значение c1 .
    • Если текущий индекс не делится на K1 или K2 , то вставьте этот индекс в вектор pos[] .
    • Если по любому индексу i количество 0 становится больше или равно 1 , то:
      • Если вектор пуст, то строку нельзя изменить до требуемой комбинации. Следовательно, напечатайте -1 .
      • В противном случае извлеките последнюю позицию, присутствующую в векторе, и обновите значение c0 как c0 – 1 и c1 как c1 + 1 и S[pos] = '1' .
  • После выполнения вышеуказанных шагов выведите строку S — измененную строку.

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

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

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