#316. 去除重复字母

• LeetCode：316. 去除重复字母
• 难度：中等
• 归类：字符串、贪心、单调栈
• 主解法：剩余次数 + 条件单调栈

#先给结论

答案必须同时满足三个条件：每种字母恰好出现一次、保持原字符串的相对顺序、字典序最小。前两个条件说明答案是 s 的某个子序列，第三个条件决定选哪一个。

用栈从左到右构造答案，每读到一个字母 letter：

1. 它已经在栈中：本次出现是重复项，直接跳过。
2. 否则，当栈顶字母比它大、且栈顶字母在后面还会出现时，弹出栈顶，把更小的 letter 提前。

一句话记忆：当前字母未入栈时，弹出所有比它大且后面还能补回的栈顶。

支撑这套规则只需要两个状态：

• remaining：每种字母在尚未扫描部分还剩多少次，用来判断"弹出后还能不能补回来"。
• stack：当前构造出的最小合法前缀。栈最多 26 个字母，判断重复直接用 stack.includes，不需要额外标记。

#题目描述

给定只包含小写英文字母的字符串 s，删除重复字母，使每种字母只出现一次。不能改变剩余字符的相对顺序，并且返回结果的字典序必须最小。

示例 1：

输入：s = "bcabc"
输出："abc"

示例 2：

输入：s = "cbacdcbc"
输出："acdb"

题目约束：

• 1 <= s.length <= 10^4。
• s 只包含小写英文字母。
• 本题与 1081「不同字符的最小子序列」相同。

#问题本质：受约束的最小子序列

删除字符不会改变其余字符的相对顺序，所以最终答案一定是 s 的子序列，而不是任意排列。

以 s = "bcabc" 为例，字母集合是 {a, b, c}，答案长度固定为 3，合法结果有 "abc"、"bac"、"bca"、"cab"。其中 "abc" 在第一个不同位置用了最小的 "a"，字典序最小。

这带来两个推论：

• 不能直接排序。 排序结果未必是原字符串的子序列，例如排序 "cba" 得到的 "abc" 无法从原串中按顺序选出。
• 困难不在去重，而在取舍。 每种字母必须恰好留一次：同一个字母的多次出现是候选，选哪一次才能让前面的位置尽可能小。这正是贪心要解决的问题。

#贪心策略：什么时候可以弹栈

扫描到当前字母 letter、栈顶为 top 时，只有同时满足下面两个条件才能弹出 top：

top > letter
并且
remaining.get(top) > 0（top 在后面还会出现）

两个条件分别回答"有没有收益"和"是否安全"，缺一不可。

#条件一：top > letter，弹栈才有收益

只有当前字母更小时，把它提前才会让第一个变化位置变小，字典序严格改善。如果 top <= letter，保留不更大的栈顶不会更差，弹栈没有意义。

#条件二：remaining.get(top) > 0，弹栈才安全

答案必须包含每种字母。弹出 top 的前提是后面还有它，可以补回来；否则结果会缺少这种字母。

例如 s = "bac"：扫描到 "a" 时虽然 "b" > "a"，但 "b" 后面不再出现（remaining.get("b") === 0）。一旦弹出 "b" 就无法补回，所以答案只能保留 "ba" 的相对顺序，返回 "bac"。

#为什么用 while 而不是 if

当前字母可能连续淘汰多个"更大且可替代"的栈顶。在 "bcabc" 中扫描到 "a" 时：

"c" > "a"，且后面还有 "c"：弹出 "c"
"b" > "a"，且后面还有 "b"：弹出 "b"

每弹出一个，新栈顶仍可能满足弹栈条件，所以要循环到不能再弹为止，才把 letter 放到它最早的安全位置。

#单调栈状态与不变量

#两个状态

• remaining.get(letter)：字母 letter 在当前扫描位置之后还会出现多少次。每读到一个字母就先扣除它的当前出现次数（即使它随后被跳过），这样弹栈判断可以直接写成 remaining.get(top) > 0。
• stack：当前选择的字母顺序，栈底到栈顶即答案顺序。判断"当前字母是否已选"直接用 stack.includes(letter)，栈最多 26 个字母，线性扫描也是常数。

注意这个栈不一定整体递增。某个较大字母如果后面不再出现就不能弹出，栈里会保留下降关系，比如答案 "acdb" 中的 "d" > "b"。所以更准确的名字是"带可行性约束的单调栈"。

#扫描过程保持的不变量

扫描任意前缀后：

1. stack 中没有重复字母，每种字母至多入选一次。
2. 栈中字母保持原字符串的相对顺序，始终是已扫描部分的子序列。
3. 被弹出的字母在未扫描后缀中至少还有一次，未来可以补回。
4. 在"能凑齐全部字母"的前提下，当前栈已是字典序最小的前缀。

扫描结束时 remaining 全为 0，任何不在栈中的字母都不可能再补回；而算法只在确保未来还有出现时才弹栈，所以最终每种字母恰好保留一次。

#示例推演

#s = "bcabc"

#s = "cbacdcbc"

最终答案是 "acdb"。

#代码实现

思路参考：JoshCrozier/leetcode-javascript。本文用 Map 统计剩余次数，并用 stack.includes 判断是否已入栈，使状态更精简；原项目采用 MIT License。

#JavaScript 实现（Map + 栈）

用 Map 直接以字母为键统计剩余次数，无需转换字符编码。栈最多 26 个字母，直接用 stack.includes(letter) 判断重复，省去额外集合的维护。

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function (s) {
    const countMap = new Map();

    for (const letter of s) {
        countMap.set(letter, (countMap.get(letter) ?? 0) + 1);
    }

    const stack = [];

    for (const letter of s) {
        // 先扣除当前出现，即使随后跳过，也必须更新剩余次数
        countMap.set(letter, countMap.get(letter) - 1);

        if (stack.includes(letter)) continue;

        // 栈顶比当前字母大，且后面还能补回时，才允许弹出
        while (
            stack.length > 0 &&
            stack[stack.length - 1] > letter &&
            countMap.get(stack[stack.length - 1]) > 0
        ) {
            stack.pop();
        }

        stack.push(letter);
    }

    return stack.join('');
};

countMap 对应前文的剩余次数状态。弹栈条件必须用 && 同时满足，检查的是栈顶字母的剩余次数；用 > 0 直接表达“后面还有”。

#代码与思路对照

#正确性说明

#每种字母恰好出现一次

入栈前的 stack.includes 检查阻止同一种字母重复入栈，所以每种字母至多出现一次。

一个字母只有在 remaining > 0 时才会被弹出，说明后面至少还有一次出现；扫描到它最后一次出现时它会重新入栈，此后 remaining === 0，不会再被弹出。因此每种出现过的字母最终至少一次、至多一次，即恰好一次。

#结果字典序最小

弹栈发生时（top > letter 且 top 可补回），把 top 延后、让更小的 letter 提前：既保持相对顺序、不丢失字母，又让第一个变化位置严格变小，所以每次弹栈都是安全且更优的交换。

停止弹栈时（top <= letter 或 top 不可补回），继续弹要么没有收益、要么破坏合法性，因此当前栈前缀已是可完成全部字母前提下的最小字典序。逐字符应用该选择，最终结果就是全局最小合法子序列。

#边界与陷阱

• 全部相同： "aaaa" 返回 "a"。
• 已经互不重复： 只能返回原字符串，不能重新排序。
• 严格递减且不重复： "cba" 仍返回 "cba"，因为每个字母都没有后续替代。
• 未来可替代： "bcabc" 中前面的 "b"、"c" 可以为 "a" 让位。
• 当前字母已在栈中： 只更新剩余次数并跳过，不能再次压栈。
• 先减少剩余次数： countMap.set(letter, countMap.get(letter) - 1) 必须在跳过重复字母之前执行，否则会把已经扫过的出现误算成未来次数。
• 两个弹栈条件都需要： 只比较字典序会漏字母，只判断未来出现则不能保证最小。
• 栈不一定整体递增： 最后一次出现的较大字母可能必须保留。

#复杂度分析

设 n = s.length：

• 统计剩余次数需要 O(n)。
• 第二轮中，每个位置上的字符至多入栈一次、出栈一次，while 总执行次数是线性规模。
• 时间复杂度：O(n)。
• 字母表固定为 26，栈和计数 Map 各自最多保存 26 个字母，额外空间复杂度 O(1)（推广到大小为 Σ 的字符集时为 O(Σ)）。

作为对照，参考的原实现在主循环中用 s.indexOf() 搜索未来位置，结果正确但隐藏了对剩余字符串的重复扫描。改用 countMap 后，未来位置查询是明确的 O(1)；成员判断用的 stack.includes 栈长不超过 26，同样是常数。

#替代解法

#最后出现位置

预处理每种字母最后一次出现的下标：

lastIndex[letter] = 该字母最后一次出现的下标

扫描到位置 i 时，弹栈条件二改为 lastIndex[top] > i。它与剩余次数方案等价，同样是 O(n) 时间、固定字母表下 O(1) 空间。

#递归选择最小首字符

找到一个最短前缀，使它已经包含后缀完成答案所需的所有字母；在其中选字典序最小字符作为答案首位，再从其后缀中删除该字符并递归。思路能解释贪心首字符的来由，但字符串切片和重复扫描成本高，不如单调栈直接。

#面试官递进追问

#1. 为什么不能直接对不同字母排序？

删除字符不能改变剩余字符的相对顺序，答案必须是原字符串的子序列。排序结果未必能从原字符串中按顺序选出。

#2. 为什么可以直接用 stack.includes 判断重复，而不需要 inStack 标记数组？

题目要求每种字母只出现一次，入栈前必须知道它是否已选。栈最多 26 个字母，includes 的线性扫描上限是常数，不影响整体 O(n)，还省掉一份必须与栈严格同步的状态。

如果字符集泛化到任意 Σ，includes 变成 O(Σ)，此时可以换用 Set 或布尔数组做显式 O(1) 查询；代价是要在入栈、弹栈时同步维护标记，忘记同步反而会引入新错误。本题 26 个小写字母的前提下，includes 是更简洁的选择。

#3. 为什么弹出较大栈顶前必须确认它还会出现？

最终答案必须包含这种字母。如果当前栈顶已经是它的最后一次可用出现，弹出后就无法补回，结果会变得非法。

#4. 为什么 countMap.set(letter, countMap.get(letter) - 1) 要在跳过重复字母之前执行？

即使当前字母已经在栈中，这次出现也已经被扫描，不能继续算作未来次数。否则后续可能错误认为还有替代出现。

#5. 为什么当前字母可以连续弹出多个栈顶？

每弹出一个较大且可替代的栈顶后，新的栈顶仍可能大于当前字母。连续交换能让当前较小字母移动到最早的安全位置。

#6. 为什么最终栈不一定严格递增？

字典序优化受“每种字母必须保留一次”约束。如果较大栈顶以后不再出现，即使当前字母更小也不能弹出它，因此可能保留下降关系。

#7. 为什么总时间是 O(n)，而不是两层循环的 O(n²)？

内层每次循环都会永久弹出一个已经入栈的字符出现。每个出现至多入栈、出栈各一次，所以所有 while 的总执行次数不超过线性规模。

#8. 这题与「移掉 K 位数字」有什么共同点和区别？

两题都用栈撤销前面较大的选择以获得更小字典序。本题必须保留每种字母且只保留一次，弹栈依赖未来是否还能补回；移掉 K 位数字则由剩余删除次数约束。

#常见错误

• 只使用集合去重，保留第一次出现，却没有优化字典序。
• 直接排序不同字母，破坏子序列顺序。
• 看到更小字符就无条件弹栈，导致某种字母丢失。
• 当前字母已经在栈中仍重复压入。
• 在跳过重复字母后才减少 remaining，使未来次数失真。
• 误以为最终栈必须严格递增。
• 在循环中反复搜索剩余字符串，却未经说明直接宣称线性复杂度。

#可迁移总结

• 唯一性约束： 入栈前先做成员查询，保证每种元素只进入答案一次；候选集合小时可直接查栈，大时再引入独立标记。
• 可撤销贪心： 当前元素更优且旧元素未来可补回时，撤销栈尾选择。
• 未来可行性： 用剩余次数或最后位置判断撤销当前选择是否安全。
• 一句话记忆： 当前字母未入栈时，弹出所有比它大且后面还能补回的栈顶。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 在 "bcabc" 中读到 "a" 时，为什么可以连续弹出 "c" 和 "b"？