Medium

题目描述

给定一个字符串 s，返回 s 的一个子序列，使得它包含 s 的所有不同字符，且只出现一次，并且按字典序最小。

示例 1：

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

示例 2：

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

提示：

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

注意： 这个问题与第 316 题相同：https://leetcode.com/problems/remove-duplicate-letters/

解题思路

这是一道经典的单调栈问题。我们需要构造一个字典序最小的子序列，包含所有不同字符且每个字符只出现一次。

核心思路是使用贪心策略：

  1. 首先统计每个字符的出现次数，这样我们知道某个字符在后面是否还会出现
  2. 遍历字符串，对于每个字符：
    • 如果已经在结果中，跳过（因为每个字符只能出现一次）
    • 否则，为了保证字典序最小，需要将栈顶比当前字符大且在后面还会出现的字符移除
    • 将当前字符加入结果

使用单调栈来维护结果序列：

  • 栈中保存当前的结果字符
  • 用一个布尔数组记录某个字符是否已经在栈中
  • 当遇到新字符时，如果栈顶字符比它大且后面还会出现，就弹出栈顶

这个算法确保了：

  1. 每个字符只出现一次（通过 inStack 数组控制）
  2. 字典序最小（通过贪心地移除不必要的大字符）
  3. 包含所有不同字符（因为我们会遍历完整个字符串）

代码实现

class Solution {
public:
    string smallestSubsequence(string s) {
        vector<int> count(26, 0);
        vector<bool> inStack(26, false);
        string result;
        
        // 统计每个字符的出现次数
        for (char c : s) {
            count[c - 'a']++;
        }
        
        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.push_back(c);
            inStack[c - 'a'] = true;
        }
        
        return result;
    }
};

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        count = {}
        in_stack = set()
        stack = []
        
        # 统计每个字符的出现次数
        for c in s:
            count[c] = count.get(c, 0) + 1
        
        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 SmallestSubsequence(string s) {
        int[] count = new int[26];
        bool[] inStack = new bool[26];
        Stack<char> stack = new Stack<char>();
        
        // 统计每个字符的出现次数
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        foreach (char c in s) {
            count[c - 'a']--;
            
            // 如果字符已经在栈中，跳过
            if (inStack[c - 'a']) continue;
            
            // 移除栈顶比当前字符大且后面还会出现的字符
            while (stack.Count > 0 && stack.Peek() > c && count[stack.Peek() - 'a'] > 0) {
                char removed = stack.Pop();
                inStack[removed - 'a'] = false;
            }
            
            stack.Push(c);
            inStack[c - 'a'] = true;
        }
        
        char[] result = new char[stack.Count];
        for (int i = result.Length - 1; i >= 0; i--) {
            result[i] = stack.Pop();
        }
        
        return new string(result);
    }
}

var smallestSubsequence = function(s) {
    const count = new Array(26).fill(0);
    const inStack = new Array(26).fill(false);
    const stack = [];
    
    // 统计每个字符的出现次数
    for (const c of s) {
        count[c.charCodeAt(0) - 97]++;
    }
    
    for (const c of s) {
        count[c.charCodeAt(0) - 97]--;
        
        // 如果字符已经在栈中，跳过
        if (inStack[c.charCodeAt(0) - 97]) continue;
        
        // 移除栈顶比当前字符大且后面还会出现的字符
        while (stack.length > 0 && stack[stack.length - 1] > c && 
               count[stack[stack.length - 1].charCodeAt(0) - 97] > 0) {
            const removed = stack.pop();
            inStack[removed.charCodeAt(0) - 97] = false;
        }
        
        stack.push(c);
        inStack[c.charCodeAt(0) - 97] = true;
    }
    
    return stack.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作复杂度
时间复杂度O(n)，其中 n 是字符串长度。每个字符最多被压入和弹出栈一次
空间复杂度O(1)，由于只有 26 个小写字母，所以额外空间是常数级别

相关题目