Лексикографически наименьшая двоичная строка, образованная путем перестановки битов по индексам, не делящимся на K1 или K2, так что количество единиц всегда больше, чем нулей слева.
Для заданной двоичной строки 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)