271. Remove Duplicate Letters
You are given a string s of lowercase English letters. Delete characters so that every distinct letter of s survives exactly once — the survivors must keep their original relative order, so the result is a subsequence of s.
Many subsequences qualify. Return the one that is smallest in dictionary (lexicographic) order.
For example, from "bcabc" both "bca" and "abc" keep one of each letter, but "abc" sorts first, so it is the answer. The smallest valid result is always unique, so there is exactly one correct output.
Example 1:
Input: s = "bcabc"
Output: "abc"
Explanation: The distinct letters are a, b, c. Keeping the a at index 2 and the later b and c gives "abc", which beats every other choice such as "bca".
Example 2:
Input: s = "cbacdcbc"
Output: "acdb"
Explanation: Distinct letters a, b, c, d. The best keepable order is a (index 2), c (index 3), d (index 4), b (index 6): "acdb". Starting with the earlier c or b can never sort lower than starting with a.
Constraints:
- 1 ≤ s.length ≤ 10⁴
- s consists of lowercase English letters only.
Hints:
Greedy on the first character: the smaller the front of the result, the smaller the whole string — but you can only pick a character if every other distinct letter still appears somewhere after it.
Build the answer on a stack. When the incoming character is smaller than the stack top, popping the top makes the result smaller — but it is only safe if that letter occurs again later. Precompute each letter's last index to check that in O(1).
Skip characters that are already in the stack: keeping the earlier occurrence is never worse, and it keeps the one-of-each invariant simple.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "bcabc"
Expected output: "abc"