题目描述
Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
Example 1:
Input: "bcabc"
Output: "abc"
Example 2:
Input: "cbacdcbc"
Output: "acdb"
题意:给一个字符串,删除其中重复的字符使得每个字符只剩一一个,并且剩下的字符串是所有可能的字符串中最小的那个。
算法1
(栈)
题解:这题的思路是这样的,我们从前往后遍历整个字符串,并用一个栈来维护当前答案:
- 如果当前字符已经在当前答案中了,直接跳过。
- 如果没有,那么我们应该将这个字符加入答案中。但是为了字典序最小,我们需要考虑是否需要弹出栈顶元素。弹出的条件则是:当前元素小于栈顶元素,并且当前栈顶元素还在后面出现过,那么栈顶元素在后面再加进来会得到更小的字典序。
这题也可以出成删除重复数字,使得剩下的数字最小。我们使用一个哈希表记录每个字母最后一次出现的位置,再用一个标记数组判断当前字符是否在答案中出现过。
string removeDuplicateLetters(string s) {
string res = "";
int n = s.length();
unordered_map<char,int> hash;
vector<int> vis(26,false);
for(int i = 0 ; i < n ; i ++)
hash[s[i]] = i;
for(int i = 0 ; i < n ; i ++)
{
if(vis[s[i] - 'a']) continue;
while(res.size() > 0 && s[i] < res.back() && i < hash[res.back()])
{
vis[res.back() - 'a'] = false;
res.pop_back();
}
res += s[i];
vis[s[i] - 'a'] = true;
}
return res;
}