Лексикографически самая большая строка, использующая не более K свопов с одинаковыми индексами четности
Для заданной строки S и положительного целого числа K задача состоит в том, чтобы найти лексикографически наибольшую возможную строку, используя не более K перестановок с условием, что переставляемые индексы должны быть либо нечетными, либо четными.
Примеры:
Input: S = “ancqz”, K = 2
Output: “zqcna“
Explanation: In one swap, we can swap characters ‘n’ and ‘q’ as they both are at even indices (2 and 4 assuming 1-based indexing). The string becomes “aqcnz”. In the second swap we can swap characters ‘a’ and ‘z’ as both have odd indices. The final string “zqcna” is the largest lexicographically possible using 2 swap operations.Note: We cannot swap for instance ‘a’ and ‘n’ or ‘n’ and ‘z’ as one of them would be at an odd index while the other at even index.
Input: S = “geeksforgeeks”, K = 3
Output: “sreksfoegeekg“
Наивный подход: наивный подход тривиален. Используйте жадный алгоритм, чтобы сделать текущий индекс максимальным, начиная слева, выбирая максимально возможный символ, который находится справа от текущего индекса, а также с той же четностью индекса, т.е. (нечетный, если текущий индекс нечетный, и четный, если текущий индекс четный). Повторите ту же процедуру не более K раз. Временная сложность подхода будет O(N 2 ) .
Эффективный подход. Приведенный выше подход можно улучшить, используя очередь с приоритетами. Выполните следующие шаги, чтобы решить проблему:
- Создайте две приоритетные очереди, одну для нечетных символов индекса, а другую для четных символов индекса.
- Перебирать символы в строке, если появляется четный символ индекса, затем искать индекс, который больше, чем текущий индекс, и символ больше, чем текущий символ в очереди приоритетов, которая содержит четные символы. Если есть, поменяйте местами два символа, нажмите текущий символ и индекс, который мы нашли в очереди приоритетов.
- Та же процедура должна быть выполнена, когда приходит нечетный символ.
- Если K становится равным 0 , завершаем цикл.
- Полученная строка будет ответом.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(NlogN)
Вспомогательное пространство: НА)