在这里插入代码片

这是一道典型的“带限制条件的字典序最小子序列”问题，需要使用单调栈+贪心的思路，同时维护必要的前缀/后缀信息，确保最终能满足长度和指定字母个数的要求。

题目理解

从字符串 s 中选取一个长度为 k 的子序列（保持字符间的相对顺序），要求：

• 子序列中至少包含 repetition 个字符 letter
• 在所有满足条件的子序列中，字典序最小

核心思路

1. 贪心 + 单调栈
   类似“移掉 K 位数字”的单调栈模型，我们希望逐位构造结果序列：
   • 如果栈顶字符比当前字符大，且弹出栈顶后仍然有足够的字符来凑齐长度 k 和满足 letter 的数量要求，则弹出栈顶，让更小的当前字符占据更靠前的位置（使字典序更小）。
2. 后缀信息预处理
   提前统计每个位置后面还剩余多少个 letter，用于判断弹出 letter 后，后面的字符是否还能补足 repetition 个 letter。
3. 弹出条件的检查
   • 剩余总字符数（包括当前） n - i 加上当前栈大小，必须能凑够 k。
   • 如果弹出的是 letter，还需要保证栈中的 letter 数 -1 再加上后缀的 letter 数 ≥ repetition。
4. 后处理
   贪心构造完后，栈中长度可能超过 k，直接截断前 k 个。
   截断后如果 letter 的数量不足，因为原字符串整体一定有足够的 letter，我们可以从结果末尾开始，把非 letter 的字符强制替换成 letter，直到满足要求（这样做的代价最小，对字典序的影响也尽可能靠后）。

完整 Java 代码

public String smallestSubsequence(String s, int k, char letter, int repetition) {
    int n = s.length();
    
    // 后缀中 letter 的个数
    int[] suffixLetter = new int[n + 1];
    for (int i = n - 1; i >= 0; i--) {
        suffixLetter[i] = suffixLetter[i + 1] + (s.charAt(i) == letter ? 1 : 0);
    }
    
    StringBuilder stack = new StringBuilder();  // 模拟栈
    int letterInStack = 0;                      // 栈中 letter 的数量
    
    for (int i = 0; i < n; i++) {
        char c = s.charAt(i);
        // 尝试弹出栈顶，让字典序更小
        while (stack.length() > 0 && stack.charAt(stack.length() - 1) > c) {
            char top = stack.charAt(stack.length() - 1);
            int restChars = n - i; // 剩余可用的字符数（包括当前字符）
            
            if (top == letter) {
                // 弹出 letter 后，还能否满足 letter 总数需求
                if (letterInStack - 1 + suffixLetter[i] >= repetition
                        && stack.length() - 1 + restChars >= k) {
                    stack.deleteCharAt(stack.length() - 1);
                    letterInStack--;
                } else {
                    break;
                }
            } else {
                if (stack.length() - 1 + restChars >= k) {
                    stack.deleteCharAt(stack.length() - 1);
                } else {
                    break;
                }
            }
        }
        // 将当前字符入栈
        stack.append(c);
        if (c == letter) letterInStack++;
    }
    
    // 截取前 k 个字符
    String res = stack.substring(0, Math.min(k, stack.length()));
    
    // 计算当前 letter 数量
    int cnt = 0;
    for (char ch : res.toCharArray()) {
        if (ch == letter) cnt++;
    }
    int need = repetition - cnt;
    
    // 如果 letter 不够，从后向前把非 letter 字符替换为 letter
    if (need > 0) {
        char[] arr = res.toCharArray();
        for (int i = arr.length - 1; i >= 0 && need > 0; i--) {
            if (arr[i] != letter) {
                arr[i] = letter;
                need--;
            }
        }
        res = new String(arr);
    }
    
    return res;
}

复杂度分析

• 时间复杂度：O(n)，每个字符最多入栈、出栈一次，预处理后缀数组为 O(n)，最终截断和替换操作也为 O(k) ≤ O(n)。
• 空间复杂度：O(n)，使用了后缀数组和栈结构。