843. Keeping One of Each Letter
A lowercase string s is given. Keep exactly ONE copy of every letter that appears in it, and
delete every other character. Among all the ways of doing that, print the alphabetically smallest
result. The surviving letters must stay in their original order.
bcabc -> abc
cbacdcbc -> acdb
leetcode -> letcod
In cbacdcbc the letters present are a, b, c and d, so the answer is four letters long. The
tempting answer abcd is impossible: after the only a, there is no b before the last c
and the last c must be used. The real answer is acdb.
## The rule, and the one extra fact it needs
This looks like problem 842, and the stack discipline is the same: hold the answer so far in non-decreasing order, and pop a larger letter when a smaller one arrives.
The difference is that a letter here may only be popped if it appears AGAIN later in the string. Popping the last copy of a letter loses it from the answer entirely, which is illegal. So the algorithm needs, for every position, whether the letter on top of the stack still occurs after the current index.
A single pass computing the LAST occurrence of each of the 26 letters answers that in constant time per check.
## The algorithm
last[c] = the final index at which letter c appears
for i from 0 to n-1, with c = s[i]:
if c is already on the stack: skip it entirely
while the stack is non-empty
and its top is > c
and last[top] > i:
pop the top, and mark it as no longer on the stack
push c, mark it as on the stack
The "already on the stack, skip" test is what keeps every letter to exactly one copy. Without it, a letter pushed early would be pushed again later and the answer would be too long.
## Why the pop is safe, and why the guard is necessary
If the top t is greater than the arriving c and t occurs again later, then dropping t
here and picking it up later puts c in an earlier position than t occupied. The two results
agree everywhere before, and at the first differing position one has c and the other has t
with c < t, so the new one is smaller. Nothing is lost, because t is still available.
If t does NOT occur again, the same exchange loses the letter t and the result is no longer
a valid answer at all. That is why the guard is not an optimisation.
## What is left on the stack
The stack, bottom to top, IS the answer. It holds one copy of each distinct letter, already in the order they must be printed.
## Related problems
Problem 842 picks a fixed LENGTH and may repeat values; here the length is fixed by the alphabet and repetition is forbidden, so the room check becomes an availability check.
## Cost
Time O(n) with a 26-entry table for last occurrences and a 26-entry table for membership.
Space O(n).
Constraints - `1 ≤ |s| ≤ 200000` - `s` contains lowercase letters only
Input
One line containing the string s, made of lowercase letters.
Output
Print one line: the alphabetically smallest string that keeps exactly one copy of every distinct letter of s and preserves their original order. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.