Задача с собеседования в Яндекс.
Вам дается строка s, которая состоит из маленьких латинских букв.
Пусть в строке k различных букв. Вы должны удалить некоторые буквы из строки s, таким образом, чтобы оставшаяся строка была лексикографически минимальным, и также имело k различных букв. (Каждый символ должен встречаться ровно один раз)

Например
s = bcdacbcd
Ответ abcd (то есть удалили буквы ***a*bcd*)


Решение:
Давайте для каждой буквы найдем правую позицию где она встречается. Из примера выше получим следующие данные.
right_pos = {a: 3, b:5, c:6, d:7}
Давайте пройдемся по строке слева направо поддерживая строку ответа.
Пусть рассматриваем букву s[i], а на префиксе набрали ответ t.
Очевидно нам стоит удалить букву t.back() (то есть последний символ в строке t), если right_pos[t.back()] > i и t.back() > s[i].
На самом деле мы будем удалять буквы с конца строки t, пока выполняется условие выше, так как все буквы, которые удалили мы можем добавить позже, ведь right_pos[t.back()] > i говорит нам о том, что справа найдется буква t.back() и мы сделали только лучше добавив символ меньше.
После добавим букву s[i] в конец строки t.
Ответ - строка t

Разберем на примере выше.
i = 0, t = b
i = 1, t = bc
i = 2, t = bcd
i = 3, t = a
i = 4, t = ac
i = 5, t = ab
i = 6, t = abc
i = 7, t = abcd
Такая идея называется монотонный стек.
Время работы алгоритма O(N).
Псевдокод в комментариях.