LeetCode Q316: Remove Duplicate Letters (hard)

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

Solution:
For explanation please refer to here. Basically, we should use greedy algorithm, try to choose the smallest character as front as possible. We use a stack to save current result string. Each time when met a totally new character is met compared to the tail of the string, if smaller than tail and the tail also shows up in the remaining part, then we can remove tail from stack and insert the new character just met. This is done iteratively.



Round 2 solution: