Войти Регистрация
Алгоритмы

209. Вычеркнуть k цифр, чтобы число стало наименьшим

Средняя

В игре в приложении Альфа‑Банка клиент получает номер купона — строку цифр code — и может вычеркнуть ровно k цифр; чем меньше оставшееся число, тем выше приз. Порядок оставшихся цифр не меняется.

Верните наименьшее возможное число строкой без ведущих нулей. Если вычеркнуты все цифры или остались одни нули, верните "0".

В работе: Сервер проверяет заявленный клиентом результат: купон из 40 цифр и k = 15 дают 4·10¹⁰ вариантов вычёркивания, а ответ нужен до анимации выигрыша.

Пример 1

Ввод
code = "7319204"
k = 3
Вывод
"1204"

Вычеркнуть 7, 3, 9: остаётся 1204.

Пример 2

Ввод
code = "10200"
k = 1
Вывод
"200"

Вычеркнуть 1 — «0200», без ведущих нулей 200.

Ограничения

  • 1 ≤ длина code ≤ 10⁵
  • 0 ≤ k ≤ длина code
  • Лимит — 2 с на тест (1500 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def smallest_after_strike(code, k):
Монотонный стекЖадный алгоритмСтрокицельO(n)

Источник: наша задача на данных Альфа-Банка. Условие пересказано своими словами.