Medium

题目描述

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= s.length <= 10^4
  • s 由小写英文字母组成

**注意：**本题与 1081 题相同。

解题思路

这是一道经典的单调栈 + 贪心算法题。

核心思路：我们需要构建一个字典序最小的去重字符串。关键在于决定何时保留当前字符，何时移除之前的字符。

算法步骤：

  1. 统计频次：首先统计每个字符在字符串中的出现次数
  2. 单调栈处理：遍历字符串，对每个字符：
    • 如果该字符已在结果中，跳过并减少计数
    • 否则，检查栈顶元素是否大于当前字符且后续还会出现，如果是则弹出栈顶
    • 将当前字符入栈并标记为已使用
  3. 贪心策略：当遇到较小字符时，如果前面较大的字符在后续还会出现，就可以安全地移除它们

为什么这样做是正确的？

  • 单调栈保证了字典序最小
  • 频次统计确保我们不会错误地移除唯一出现的字符
  • 贪心策略保证每次都做出局部最优选择

时间复杂度O(n)，空间复杂度O(1)（因为最多26个字母）。

代码实现

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> count(26, 0);
        vector<bool> inStack(26, false);
        
        // 统计每个字符的出现次数
        for (char c : s) {
            count[c - 'a']++;
        }
        
        string result = "";
        
        for (char c : s) {
            count[c - 'a']--;
            
            // 如果字符已经在结果中，跳过
            if (inStack[c - 'a']) {
                continue;
            }
            
            // 当栈顶字符大于当前字符且后面还会出现时，弹出栈顶
            while (!result.empty() && result.back() > c && count[result.back() - 'a'] > 0) {
                inStack[result.back() - 'a'] = false;
                result.pop_back();
            }
            
            result += c;
            inStack[c - 'a'] = true;
        }
        
        return result;
    }
};

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # 统计每个字符的出现次数
        count = {}
        for c in s:
            count[c] = count.get(c, 0) + 1
        
        stack = []
        in_stack = set()
        
        for c in s:
            count[c] -= 1
            
            # 如果字符已经在栈中，跳过
            if c in in_stack:
                continue
            
            # 当栈顶字符大于当前字符且后面还会出现时，弹出栈顶
            while stack and stack[-1] > c and count[stack[-1]] > 0:
                removed = stack.pop()
                in_stack.remove(removed)
            
            stack.append(c)
            in_stack.add(c)
        
        return ''.join(stack)

public class Solution {
    public string RemoveDuplicateLetters(string s) {
        int[] count = new int[26];
        bool[] inStack = new bool[26];
        
        // 统计每个字符的出现次数
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        List<char> stack = new List<char>();
        
        foreach (char c in s) {
            count[c - 'a']--;
            
            // 如果字符已经在栈中，跳过
            if (inStack[c - 'a']) {
                continue;
            }
            
            // 当栈顶字符大于当前字符且后面还会出现时，弹出栈顶
            while (stack.Count > 0 && stack[stack.Count - 1] > c && count[stack[stack.Count - 1] - 'a'] > 0) {
                char removed = stack[stack.Count - 1];
                stack.RemoveAt(stack.Count - 1);
                inStack[removed - 'a'] = false;
            }
            
            stack.Add(c);
            inStack[c - 'a'] = true;
        }
        
        return new string(stack.ToArray());
    }
}

var removeDuplicateLetters = function(s) {
    const count = new Map();
    const inStack = new Set();
    
    // 统计每个字符的出现次数
    for (const c of s) {
        count.set(c, (count.get(c) || 0) + 1);
    }
    
    const stack = [];
    
    for (const c of s) {
        count.set(c, count.get(c) - 1);
        
        // 如果字符已经在栈中，跳过
        if (inStack.has(c)) {
            continue;
        }
        
        // 当栈顶字符大于当前字符且后面还会出现时，弹出栈顶
        while (stack.length > 0 && stack[stack.length - 1] > c && count.get(stack[stack.length - 1]) > 0) {
            const removed = stack.pop();
            inStack.delete(removed);
        }
        
        stack.push(c);
        inStack.add(c);
    }
    
    return stack.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个字符最多入栈和出栈一次
空间复杂度O(1)使用固定大小的数组和集合（最多26个字母）

相关题目