题目描述
给定一个仅包含小写字母的字符串,去除字符串中重复的字母,使得每个字母只出现一次。需保证返回结果的字典序最小(要求不能打乱其他字符的相对位置)。
样例
输入:"bcabc"
输出:"abc"
输入:"cbacdcbc"
输出:"acdb"
算法
(贪心,栈) $O(n)$
- 使用栈来贪心的构造最终的字符串,栈的更新规则如下。
- 前提是当前字符没有在栈中出现。如果当前字符比栈顶字符的值小,且栈顶字符不是最后一次出现,则栈顶出栈。
- 重复 2 直到栈空或栈顶不满足出栈条件。此时,将当前字符压入栈中,且标记当前字符出现过。
- 最后将栈中元素从栈底到栈顶的顺序输出。
时间复杂度
- 预处理字符最后出现的位置为 $O(n)$。
- 每个元素最多进栈一次,出栈一次,故总时间复杂度为 $O(n)$。
空间复杂度
- 使用了栈来存储当前答案,但栈的大小最长不超过 26。
- 其他辅助和标记数组的长度都是 26,最后答案的长度也不超过 26。
- 所以可以认为空间复杂度为 $O(1)$。
C++ 代码
class Solution {
public:
string removeDuplicateLetters(string s) {
vector<int> last(26, -1);
vector<char> st;
vector<bool> vis(26, false);
int n = s.length();
for (int i = 0; i < n; i++)
last[s[i] - 'a'] = i;
for (int i = 0; i < n; i++) {
if (vis[s[i] - 'a'])
continue;
while (!st.empty() && st.back() > s[i]) {
if (last[st.back() - 'a'] < i)
break;
vis[st.back() - 'a'] = false;
st.pop_back();
}
st.push_back(s[i]);
vis[s[i] - 'a'] = true;
}
string ans;
for (char c : st)
ans += c;
return ans;
}
};