Hard

题目描述

给你一个字符串 s、一个整数 k、一个字母 letter 以及一个整数 repetition。

返回 s 中长度为 k 且字典序最小的子序列，该子序列同时应满足字母 letter 出现至少 repetition 次。

生成的测试用例满足 letter 在 s 中至少出现 repetition 次。

子序列是一个可以通过删除原字符串中的某些字符而不改变剩余字符顺序的字符串。

如果字符串 a 在第一个不同的位置比字符串 b 的对应字母在字母表中更靠前，则字符串 a 字典序比字符串 b 小。

示例 1：

输入：s = "leet", k = 3, letter = "e", repetition = 1
输出："eet"
解释：长度为 3 且字母 'e' 至少出现 1 次的子序列有四个：
- "lee"（从 "leet" 中得出）
- "let"（从 "leet" 中得出）
- "let"（从 "leet" 中得出）
- "eet"（从 "leet" 中得出）
其中字典序最小的是 "eet"。

示例 2：

输入：s = "leetcode", k = 4, letter = "e", repetition = 2
输出："ecde"
解释："ecde" 是长度为 4 且字母 "e" 至少出现 2 次的字典序最小子序列。

示例 3：

输入：s = "bb", k = 2, letter = "b", repetition = 2
输出："bb"
解释："bb" 是长度为 2 且字母 "b" 至少出现 2 次的唯一子序列。

提示：

  • 1 <= repetition <= k <= s.length <= 5 * 10^4
  • s 由小写英文字母组成
  • letter 是一个小写英文字母，在 s 中至少出现 repetition 次

解题思路

这是一个经典的单调栈问题，需要同时考虑字典序最小和特定字符出现次数的约束。

核心思路：

  1. 使用单调栈维护字典序最小的子序列
  2. 预处理计算每个位置后面还有多少个目标字符 letter
  3. 对于每个字符，决定是否可以弹出栈顶元素来获得更小的字典序

关键约束处理：

  • 长度约束：栈的大小不能超过 k，且最终必须达到 k
  • 字符出现次数约束：目标字符 letter 必须至少出现 repetition 次

弹出条件： 当考虑弹出栈顶元素时，需要同时满足：

  1. 当前字符小于栈顶字符（字典序优化）
  2. 栈的长度 + 剩余可选字符数 > k（确保能凑够 k 个字符）
  3. 如果栈顶是目标字符，弹出后仍能满足 repetition 约束

添加条件： 只有当栈未满（长度 < k）时才添加字符，优先添加目标字符以满足约束。

时间复杂度为 O(n)，空间复杂度为 O(n)，其中 n 是字符串长度。

代码实现

class Solution {
public:
    string smallestSubsequence(string s, int k, char letter, int repetition) {
        int n = s.length();
        vector<int> letterCount(n, 0);
        
        // 计算每个位置后面还有多少个目标字符
        int count = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == letter) count++;
            letterCount[i] = count;
        }
        
        string stack;
        int letterInStack = 0;
        
        for (int i = 0; i < n; i++) {
            // 尝试弹出栈顶元素以获得更小字典序
            while (!stack.empty() && 
                   stack.back() > s[i] && 
                   stack.size() + (n - i) > k && 
                   (stack.back() != letter || letterInStack + letterCount[i] > repetition)) {
                if (stack.back() == letter) {
                    letterInStack--;
                }
                stack.pop_back();
            }
            
            // 添加当前字符（如果栈未满）
            if (stack.size() < k) {
                stack.push_back(s[i]);
                if (s[i] == letter) {
                    letterInStack++;
                }
            }
        }
        
        return stack;
    }
};

class Solution:
    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:
        n = len(s)
        letter_count = [0] * n
        
        # 计算每个位置后面还有多少个目标字符
        count = 0
        for i in range(n - 1, -1, -1):
            if s[i] == letter:
                count += 1
            letter_count[i] = count
        
        stack = []
        letter_in_stack = 0
        
        for i in range(n):
            # 尝试弹出栈顶元素以获得更小字典序
            while (stack and 
                   stack[-1] > s[i] and 
                   len(stack) + (n - i) > k and 
                   (stack[-1] != letter or letter_in_stack + letter_count[i] > repetition)):
                if stack[-1] == letter:
                    letter_in_stack -= 1
                stack.pop()
            
            # 添加当前字符（如果栈未满）
            if len(stack) < k:
                stack.append(s[i])
                if s[i] == letter:
                    letter_in_stack += 1
        
        return ''.join(stack)

public class Solution {
    public string SmallestSubsequence(string s, int k, char letter, int repetition) {
        int n = s.Length;
        int[] letterCount = new int[n];
        
        // 计算每个位置后面还有多少个目标字符
        int count = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == letter) count++;
            letterCount[i] = count;
        }
        
        List<char> stack = new List<char>();
        int letterInStack = 0;
        
        for (int i = 0; i < n; i++) {
            // 尝试弹出栈顶元素以获得更小字典序
            while (stack.Count > 0 && 
                   stack[stack.Count - 1] > s[i] && 
                   stack.Count + (n - i) > k && 
                   (stack[stack.Count - 1] != letter || letterInStack + letterCount[i] > repetition)) {
                if (stack[stack.Count - 1] == letter) {
                    letterInStack--;
                }
                stack.RemoveAt(stack.Count - 1);
            }
            
            // 添加当前字符（如果栈未满）
            if (stack.Count < k) {
                stack.Add(s[i]);
                if (s[i] == letter) {
                    letterInStack++;
                }
            }
        }
        
        return new string(stack.ToArray());
    }
}

var smallestSubsequence = function(s, k, letter, repetition) {
    const n = s.length;
    const letterCount = new Array(n).fill(0);
    
    // 计算每个位置后面还有多少个目标字符
    let count = 0;
    for (let i = n - 1; i >= 0; i--) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)每个字符最多入栈和出栈各一次，预处理需要O(n)
空间复杂度O(n)需要额外的数组存储后缀字符计数和栈空间

相关题目