316. 去除重复字母

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

先给结论

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

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

它已经在栈中：本次出现是重复项，直接跳过。
否则，当栈顶字母比它大、且栈顶字母在后面还会出现时，弹出栈顶，把更小的 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[top] > 0（top 在后面还会出现）

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

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

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

条件二：`remaining[top] > 0`，弹栈才安全

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

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

为什么用`while` 而不是`if`

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

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

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

单调栈状态与不变量

两个状态

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

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

扫描过程保持的不变量

扫描任意前缀后：

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

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

示例推演

`s = "bcabc"`

当前字母	扫描后剩余次数	操作	栈
`b`	后面还有 `b`	入栈	`b`
`c`	后面还有 `c`	入栈	`bc`
`a`	`b`、`c` 后面都还有	依次弹出 `c`、`b`，压入 `a`	`a`
`b`	后面没有 `b`	入栈	`ab`
`c`	后面没有 `c`	入栈	`abc`

`s = "cbacdcbc"`

当前字母	操作	栈
`c`	入栈	`c`
`b`	`c` 以后还会出现，弹出 `c`	`b`
`a`	`b` 以后还会出现，弹出 `b`	`a`
`c`	入栈	`ac`
`d`	入栈	`acd`
`c`	已在栈中，跳过	`acd`
`b`	`d` 后面不再出现，不能弹出；压入 `b`	`acdb`
`c`	已在栈中，跳过	`acdb`

最终答案是 "acdb"。

代码实现

思路参考：JoshCrozier/leetcode-javascript。本文将未来位置与成员关系的重复字符串扫描改为计数数组和布尔数组，使状态含义和线性复杂度更直接；原项目采用 MIT License。

JavaScript 实现

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function (s) {
    // 题目保证只含小写英文字母，固定 26 种，可用定长数组做计数与标记
    const alphabetSize = 26;

    // remaining[i]：字母 i 在“尚未扫描部分”还剩多少次
    // 弹栈时用它判断栈顶字母以后还能不能补回来
    const remaining = new Array(alphabetSize).fill(0);

    // 当前构造出的最小合法前缀，栈底到栈顶即答案顺序
    const stack = [];

    // 第一轮：统计每种字母的总出现次数
    // 'a' 的 charCode 是 97，减去 97 得到 0~25 的下标
    for (const letter of s) {
        remaining[letter.charCodeAt(0) - 97]++;
    }

    // 第二轮：从左到右扫描，贪心构造答案
    for (const letter of s) {
        const index = letter.charCodeAt(0) - 97;

        // 先扣除当前这次出现：
        // remaining 必须表示“当前字符之后”的后缀次数，
        // 即使当前字母已在栈中会被跳过，这次出现也不能再算作未来次数
        remaining[index]--;

        // 当前字母已在栈中：本次出现是重复项，直接跳过，
        // 保证每种字母只入栈一次。栈最多 26 个字母，includes 是常数时间
        if (stack.includes(letter)) {
            continue;
        }

        // 尝试用当前较小字母淘汰栈尾：
        // 只要栈顶比当前字母大、且栈顶字母在后面还会出现，
        // 就把它弹出，让更小的 letter 占到更靠前的位置
        while (stack.length > 0) {
            const top = stack[stack.length - 1];
            const topIndex = top.charCodeAt(0) - 97;

            // 停止条件（满足其一即停）：
            // 1. top <= letter：栈顶不比当前字母大，提前 letter 不会更优
            // 2. remaining[topIndex] === 0：栈顶是该字母最后一次出现，
            //    弹出后无法补回，结果会缺少这种字母
            if (top <= letter || remaining[topIndex] === 0) {
                break;
            }

            // 弹出栈顶，它在后面还会出现，允许以后重新入栈
            stack.pop();
        }

        // 当前字母正式入选
        stack.push(letter);
    }

    // 栈底到栈顶的顺序就是字典序最小的合法子序列
    return stack.join('');
};

不用`charCode` 的 Map 写法

charCodeAt 只是把字母映射成数组下标的手段，不是必需的。用 Map 计数，字母本身就是键，逻辑完全一致；字母之间的大小比较用字符串比较即可，字典序天然正确。

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function (s) {
    // remaining：每种字母在“尚未扫描部分”还剩多少次
    // 弹栈时用它判断栈顶字母以后还能不能补回来
    const remaining = new Map();

    // 当前构造出的最小合法前缀，栈底到栈顶即答案顺序
    const stack = [];

    // 第一轮：统计每种字母的总出现次数，字母本身就是键
    for (const letter of s) {
        remaining.set(letter, (remaining.get(letter) ?? 0) + 1);
    }

    // 第二轮：从左到右扫描，贪心构造答案
    for (const letter of s) {
        // 先扣除当前这次出现：
        // remaining 必须表示“当前字符之后”的后缀次数，
        // 即使当前字母已在栈中会被跳过，这次出现也不能再算作未来次数
        remaining.set(letter, remaining.get(letter) - 1);

        // 当前字母已在栈中：本次出现是重复项，直接跳过，
        // 保证每种字母只入栈一次。栈最多 26 个字母，includes 是常数时间
        if (stack.includes(letter)) {
            continue;
        }

        // 尝试用当前较小字母淘汰栈尾：
        // 只要栈顶比当前字母大、且栈顶字母在后面还会出现，
        // 就把它弹出，让更小的 letter 占到更靠前的位置
        while (stack.length > 0) {
            const top = stack[stack.length - 1];

            // 停止条件（满足其一即停）：
            // 1. top <= letter：栈顶不比当前字母大，提前 letter 不会更优
            //    （字符串比较即字典序比较，无需 charCode）
            // 2. remaining.get(top) === 0：栈顶是该字母最后一次出现，
            //    弹出后无法补回，结果会缺少这种字母
            if (top <= letter || remaining.get(top) === 0) {
                break;
            }

            // 弹出栈顶，它在后面还会出现，允许以后重新入栈
            stack.pop();
        }

        // 当前字母正式入选
        stack.push(letter);
    }

    // 栈底到栈顶的顺序就是字典序最小的合法子序列
    return stack.join('');
};

两种写法复杂度相同，取舍在于：

数组版：访问更快、更省内存，但依赖"只有 26 个小写字母"的前提。
Map 版：不假设字符集，换成任意字符也能工作，常数开销略大。

代码与思路对照

代码	作用
第一轮统计 `remaining`	预先知道每种字母的总出现次数
`remaining[index]--`	将当前出现从“未来次数”中扣除
`stack.includes(letter)`	跳过已经选择的重复字母
`top > letter`	条件一：当前较小字母提前后能改善字典序
`remaining[topIndex] > 0`	条件二：被弹出的字母以后仍能补回
`stack.join('')`	栈内顺序就是最终最小子序列

正确性说明

每种字母恰好出现一次

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

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

结果字典序最小

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

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

边界与陷阱

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

复杂度分析

设 n = s.length：

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

作为对照，参考的原实现在主循环中用 s.indexOf() 搜索未来位置，结果正确但隐藏了对剩余字符串的重复扫描。改用 remaining 后，未来位置查询是明确的 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. 为什么`remaining[index]--` 要在跳过重复字母之前执行？

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

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

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

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

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

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

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

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

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

常见错误

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

可迁移总结

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

刷题后自测

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

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

在 "bac" 中读到 "a" 时，为什么不能弹出 "b"？

为什么本题用 stack.includes 判断重复不影响时间复杂度？

尝试把 remaining 改写成 lastIndex，并写出对应弹栈条件。

ON THIS PAGE

#316. 去除重复字母

#先给结论

#题目描述

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

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

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

#条件二：remaining[top] > 0，弹栈才安全

#为什么用while 而不是if

#单调栈状态与不变量

#两个状态

#扫描过程保持的不变量

#示例推演

#s = "bcabc"

#s = "cbacdcbc"

#代码实现

#JavaScript 实现

#不用charCode 的 Map 写法

#代码与思路对照

#正确性说明

#每种字母恰好出现一次

#结果字典序最小

#边界与陷阱

#复杂度分析

#替代解法

#最后出现位置

#递归选择最小首字符

#面试官递进追问

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

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

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

#4. 为什么remaining[index]-- 要在跳过重复字母之前执行？

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

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

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

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

#常见错误

#可迁移总结

#刷题后自测