摘要：
一道贪心题。
题目
给你一个字符串 $s$ ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
注意：该题与 LeetCode 1081. 不同字符的最小子序列 相同
示例 1：
输入：s = “bcabc”
输出：”abc”
示例 2：
输入：s = “cbacdcbc”
输出：”acdb”
提示：
- $1 <= s.length <= 10^4$
- $s$ 由小写英文字母组成
贪心
首先将每个字符最后出现的位置记录下来，维护一个答案字符串。对于原字符串的每一个字符，判断答案字符串的最后一个字符是否大于它。如果大于它，而且这个字符在后面出现过，那么这个字符就不是最优的，要剔除。如果小于，则直接放入答案字符串。
如何证明方法的正确性？
现设想全部字符不重复，那么因为答案需要维护原字符之间的相对位置，那么答案就是原字符串。
如果其中的某些字符出现重复，那么当一个字符在之后的地方出现过，那么该字符在前面就是可被替换的。
现在考虑如果一个字符在之后也出现了，那么什么时候它可以被替换？
那就是它后方出现了一个比它小的新字符，那么现在需要作出决策，要么替换前方的在后面重复出现的字符，要么直接加在后面。
显然，替换掉属于最优解，因为只有这样整体字典序最小，且后面可以使用重复字符补上，不会改变字符之间的相对位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public:
string removeDuplicateLetters(string s) {
string stk;
unordered_map<char, bool> ins;
unordered_map<char, int> last;
int n = s.size();
for (int i = 0; i < n; i ++) last[s[i]] = i;
for (int i = 0; i < n; i ++) {
if (ins[s[i]]) continue;
for (; stk.size() && stk.back() > s[i] && last[stk.back()] > i;) {
ins[stk.back()] = false;
stk.pop_back();
}
stk += s[i];
ins[s[i]] = true;
}
return stk;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution {
public:
static constexpr int N = 123;
int last[N], st[N];
string stk;
string removeDuplicateLetters(string s) {
int len = s.size();
for (int i = 0; i < len; i++) {
last[s[i]] = i;
}
for (int i = 0; i < len; i++) {
if (st[s[i]]) continue;
for (; stk.size() && s[i] < stk.back() && last[stk.back()] > i;) {
st[stk.back()] = 0;
stk.pop_back();
}
stk += s[i];
st[s[i]] = 1;
}
return stk;
}
};
|