Remove Duplicate Letters -- LeetCode

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"

思路：采用贪心算法，对于给定的字符串S，找到所有结果的最小前缀(即最小的字母)，假如有多个最小前缀，则选择最左侧的。

令最终选择的最小前缀的下标为pos，则删掉s[pos]左侧的所有字符，并删掉剩下字符串中所有与s[pos]相等的字符。

C++中将某个特定字符从所有出现的位置删掉可以这样实现：

s.erase(remove(s.begin(), s.end(), theCharacterNeedtoRemove), s.end());

其中remove函数需要使用algorithm库文件。算法复杂度为O(26 * n) = O(n)

 1 class Solution {
 2 public:
 3     string removeDuplicateLetters(string s) {
 4         vector<int> alp(26, -1);
 5         for (int i = 0, n = s.size(); i < n; i++)
 6             alp[(int)(s[i] - 'a')] = i;
 7         int pos = -1;
 8         for (int i = 0, n = s.size(); i < n; i++)
 9         {
10             int ind = (int)(s[i] - 'a');
11             if (alp[ind] == -1) continue;
12             if (pos == -1 || s[pos] > s[i]) pos = i;
13             if (alp[ind] == i) break;
14         }
15         if (s == "" || pos == -1) return "";
16         char cand = s[pos];
17         s = s.substr(pos + 1);
18         s.erase(remove(s.begin(), s.end(), cand), s.end());
19         return cand + removeDuplicateLetters(s);
20     }
21 };