316. 去除重复字母

🟠   🔖  栈 贪心 字符串 单调栈  🔗 力扣 LeetCode

题目

Given a string s, 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: s = "bcabc"

Output: "abc"

Example 2:

Input: s = "cbacdcbc"

Output: "acdb"

Constraints:

• 1 <= s.length <= 10^4
• s consists of lowercase English letters.

注意： 本题与 LeetCode 第 1081 题 相同。

题目大意

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

比如说输入字符串 s = "babc"，去重且符合相对位置的字符串有两个，分别是 "bac" 和 "abc"，但是我们的算法得返回 "abc"，因为它的字典序更小。

解题思路

哈希表 + 单调栈

题目有三个要求：去重、不能打乱其他字符顺序、字典序最小。

1. 去重：可以通过 「使用哈希表存储字母出现次数」 的方式，将每个字母出现的次数统计起来，再遍历一遍，去除重复的字母。
2. 不能打乱其他字符顺序：按顺序遍历，将非重复的字母存储到答案数组或者栈中，最后再拼接起来，就能保证不打乱其他字符顺序。
3. 字典序最小：意味着字典序小的字母应该尽可能放在前面。
   1. 对于第 i 个字符 s[i] 而言，如果第 0 ~ i - 1 之间的某个字符 s[j] 在 s[i] 之后不再出现了，那么 s[j] 必须放到 s[i] 之前。
   2. 而如果 s[j] 在之后还会出现，并且 s[j] 的字典序大于 s[i]，我们则可以先舍弃 s[j]，把 s[i] 尽可能的放到前面。后边再考虑使用 s[j] 所对应的字符。

要满足第 3 条需求，我们可以使用 「单调栈」 来解决。我们使用单调栈存储 s[i] 之前出现的非重复、并且字典序最小的字符序列。整个算法步骤如下：

1. 先遍历一遍字符串，用哈希表 count 统计出每个字母出现的次数。
2. 然后使用单调递减栈保存当前字符之前出现的非重复、并且字典序最小的字符序列。
3. 当遍历到 s[i] 时，如果 s[i] 没有在栈中出现过(使用哈希表 inStack 标记)：
   1. 比较 s[i] 和栈顶元素的字典序。如果 s[i] 的字典序小于栈顶元素，并且栈顶元素之后的出现次数大于 0，则将栈顶元素弹出。
   2. 然后继续判断 s[i] 和栈顶元素，直到栈顶元素出现次数为 0 时停止弹出。此时将 s[i] 添加到单调栈中。
4. 从哈希表 count 中减去 s[i] 出现的次数，继续遍历。
5. 最后将单调栈中的字符依次拼接为答案字符串，并返回。

代码

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function (s) {
	let count = new Map();
	let inStack = new Map();
	let stack = [];
	for (let i of s) {
		let val = count.get(i) || 0;
		count.set(i, val + 1);
	}
	for (let i of s) {
		count.set(i, count.get(i) - 1);
		if (!inStack.get(i)) {
			let top = stack[stack.length - 1];
			while (top && i < top && count.has(top) && count.get(top) > 0) {
				stack.pop();
				inStack.set(top, false);
				top = stack[stack.length - 1];
			}
			stack.push(i);
			inStack.set(i, true);
		}
	}
	return stack.join('');
};

相关题目

题号	标题	题解	标签	难度
2030	含特定字母的最小子序列		栈 贪心 字符串 1+