Новое — это хорошо забытое старое

Рассмотрим 2 случая:

  1. Если n < k, то надо приписать в конец исходной строки k - n минимальных символов из s.
  2. Если n ≥ k, то надо суффикс строки, состоящий из первых k символов исходной строки, из самых больших символов заменить на самые минимальные символы, а следующий символ после этого суффикса увеличить до следующего в алфавите символа, присутствующего в исходной строке.

Асимптотика .