[LeetCode]Remove Duplicate Letters

这道题要求字典序最小的结果。但是在我们尽量求小的同时，我们还需要注意在扫过某个字符c最后出现的位置之前要保证一定取过c。为了满足这一点，我们的策略是，首先求出所有字符最后出现的位置lastPos，比如对于字符串caccabad，我们有lastPos = [c->3, b->5, a->6, d->7]。我们每次取lastPos中取最小的value pos，我们有currLeft初始值为0，每次在[currLeft, pos]的区间去最小的char加入结果集。之后更新currLeft = pos + 1，并且remove lastPos中对于的entry，并且重复上述的步骤，注意已经取过的字符我们要跳过。这样我们可以保证满足在扫过某个字符c最后出现的位置之前取过c并且使得字典序最小，因为我们每次都是取满足条件的最小值。同样对于例子s = caccabad：

1. 首先pos = 3，currLeft = 0，[0, 3]中我们取到最小值s[1] = a。currLeft = 2，lastPos remove a
2. pos仍然为3，currLeft = 2，[2, 3]中最小值s[2] = c。currLeft = 3，lastPos remove c，发现我们现在应该更新pos，因为c我们已经取过了，就不需要在意c最后出现的位置了，我们应该关注下一个。pos = 5。
3. pos = 5， currLeft = 3，[3, 5]中最小值并且之前没有出现过的只有s[5] = b。currLeft = 6，lastPos remove b，同理更新pos = 7，因为此时lastPos只剩下d了。
4. pos = 7，currLeft = 6，[6, 7]中最小值并且之前没有出现过的只有s[7] = d。
5. 找到答案acbd，跳出循环。

循环的过程中可能会回溯，1步骤中我们扫了[0, 3]，第二步中我们又重复扫了[2,3]，但是鉴于总共有26个字符，所以时间复杂度为O(26 * n) = O(n)，空间复杂度O(n)，代码如下：

循环：

递归：