Smallest word of distinct letters
Build the alphabetically smallest string that uses every distinct letter of the text exactly once, keeping the letters in their original order. About 20 minutes.
Pop only if it comes again
You want the smallest word that contains each distinct letter once, in an order the text allows. As with removing digits, when a smaller letter arrives, bigger letters on top of the stack would be better placed later.
But a letter may only be popped if another copy of it comes later in the text. Otherwise the word would lose that letter for good. So first record the last position of each letter.
last = {}
for i, ch in enumerate("abcab"):
last[ch] = i
# {"a": 3, "b": 4, "c": 2}b is pushed. Stack: b.
Skip letters you already hold
Keep a set of the letters now in the stack. When a letter arrives that is already in the stack, skip it. The copy in the stack is already in the best place it can be at this point.
Otherwise do the pops, then push the letter and add it to the set. When the text ends, the stack read from bottom to top is the answer.
if ch in seen:
continueWhy not pop d when b arrives?
- AThere is no d later in the text, so popping it would lose the letter
- Bd is smaller than b
- Cd is already in the stack twice
Show the answer
There is no d later in the text, so popping it would lose the letter. Every distinct letter must be used once.
Remove duplicate letters
Given a string s of lowercase letters, remove duplicate letters so that every letter appears exactly once, and the result is the smallest in alphabetical order among all possible results. The letters of the result must appear in the same relative order as in s.
s = "cbacdcbc" → "acdb"
1 ≤ length of s ≤ 100,000 · s has only lowercase letters