Лексикографически наибольшая строка, возможная не более чем за K замен

Для заданной строки S длины N , состоящей из строчных букв, задача состоит в том, чтобы найти лексикографически самую длинную строку, которая может быть получена заменой не более чем K символов из заданной строки.

Примеры:

Input: S = “dbza”, K = 1 
Output: zbza 
Explanation: Replace S[0] (= ‘d’) with ‘z’ to obtain the lexicographically largest string.

Input: S = “zzzz”, K = 2 
Output: zzzz

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

• Запустите цикл для i = 0 до длины строки:
  • Если текущий символ не равен z , а K не равен 0:
    • Затем замените текущий символ на z .
    • К = К – 1.
• Наконец, верните измененную строку.

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

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