跳至主要內容

1081. 不同字符的最小子序列


1081. 不同字符的最小子序列open in new window

🟠   🔖  贪心 字符串 单调栈  🔗 力扣open in new window LeetCodeopen in new window

题目

Given a string s, return the lexicographically smallest subsequenceof s that contains all the distinct characters of s exactly once.

Example 1:

Input: s = "bcabc"

Output: "abc"

Example 2:

Input: s = "cbacdcbc"

Output: "acdb"

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.

Note: This question is the same as 316

题目大意

给你一个字符串 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('');
};

相关题目

题号标题题解标签难度
1673找出最具竞争力的子序列open in new window 贪心 数组 1+