思路总览

问题拆解

我们要通过删除尽可能少的字符，使 26 个字母的出现次数满足

在所有最少删除的方案中，再要求得到的字符串字典序最小。

这可分两步：

1. 确定保留的各字母配额 $c[0..25]$：在原始频次 $f[0..25]$ 下，找一个不降序并且不超过 $f$ 的向量 $c$，使 $\sum c_i$ 最大（即删除最少）。
2. 按配额取字典序最小的子序列：在字符串中选取恰好 $c[i]$ 个字母 $i$ 的子序列，使结果字典序最小。

最少删除 —— 右向单调“截顶”

不降序即 $c[i]\le c[i+1]$。为了使 $\sum c_i$ 最大，只需取按字母序从右往左的最大可行值：

• 令 $c[25]=f[25]$；
• 对 $i=24\ldots 0$：$c[i]=\min\big(f[i],\,c[i+1]\big)$ 这得到的是逐位不超过 $f$ 的最大不降序向量，从而保证删除最少。

直观理解：右边（靠近 z）的配额越大越好，左边（靠近 a）最多只能跟上右边，不得超过自身上界 $f[i]$。

字典序最小子序列 —— 单调栈 + 配额可行性

已知每个字母要取的配额 need[i]=c[i]，同时有全串剩余可供选择 remain[i]=f[i]。从左到右扫描原串，维护一个字符栈（即当前答案）：

1. 到达字符 ch 时，先 remain[ch]--。
2. 若 need[ch]==0，说明 ch 已取够，跳过。
3. 否则，尝试弹栈以变字典序更小： 当栈顶字符 top > ch 且即使丢掉一个 top，后面也还能补足配额时（判断条件：remain[top] >= need[top] + 1），就弹出 top，并把 need[top]++（因为被弹走后仍需再取一个）。
4. 把 ch 入栈，need[ch]--。

扫描结束，栈中字符串即为满足配额的字典序最小子序列。

复杂度分析

• 统计与配额：$O(26)$。
• 单调栈扫描：每个字符最多被入栈、出栈各一次，$O(n)$。
• 总时间复杂度：$O(n)$，空间复杂度：$O(n)$（输出所需）+ $O(26)$。

代码

Python 实现

# 读取输入，O(n) 贪心 + 单调栈
import sys

def solve():
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    s = data[1].strip()
    base = ord('a')

    # 频次
    f = [0]*26
    for ch in s:
        f[ord(ch)-base] += 1

    # 配额 c：从右到左截顶
    c = [0]*26
    c[25] = f[25]
    for i in range(24, -1, -1):
        c[i] = min(f[i], c[i+1])

    need = c[:]             # 还需要取的个数
    remain = f[:]           # 剩余可用个数（未扫描的）
    st = []                 # 结果栈（字符）

    for ch in s:
        i = ord(ch) - base
        remain[i] -= 1
        if need[i] == 0:
            continue  # 已满足该字母配额，跳过

        # 弹栈：让字典序更小，且保证可行
        while st:
            t = st[-1]
            ti = ord(t) - base
            if t <= ch:
                break
            # 若把一个 t 弹了，后面还能补足 need[t]+1 吗？
            if remain[ti] >= need[ti] + 1:
                st.pop()
                need[ti] += 1
            else:
                break

        st.append(ch)
        need[i] -= 1

    print(''.join(st))

if __name__ == "__main__":
    solve()

Java 实现

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String s = br.readLine().trim();

        int[] f = new int[26];
        for (int idx = 0; idx < s.length(); idx++) f[s.charAt(idx) - 'a']++;

        // 右到左截顶，得到最少删除的配额 c
        int[] c = new int[26];
        c[25] = f[25];
        for (int i = 24; i >= 0; i--) c[i] = Math.min(f[i], c[i + 1]);

        int[] need = c.clone();
        int[] remain = f.clone();

        char[] st = new char[n]; // 栈
        int top = -1;

        for (int idx = 0; idx < s.length(); idx++) {
            char ch = s.charAt(idx);
            int id = ch - 'a';
            remain[id]--;

            if (need[id] == 0) continue; // 不再需要该字母

            // 弹栈：让字典序更小，且保证配额可行
            while (top >= 0) {
                char t = st[top];
                if (t <= ch) break;
                int tid = t - 'a';
                if (remain[tid] >= need[tid] + 1) {
                    top--;
                    need[tid]++; // 被弹出，后续还需再取一个
                } else break;
            }

            st[++top] = ch;
            need[id]--;
        }

        System.out.println(new String(st, 0, top + 1));
    }
}

C++ 实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    string s; cin >> s;

    vector<int> f(26, 0);
    for (char ch : s) f[ch - 'a']++;

    // 配额 c：从右到左 min 截顶
    vector<int> c(26, 0);
    c[25] = f[25];
    for (int i = 24; i >= 0; --i) c[i] = min(f[i], c[i + 1]);

    vector<int> need = c, remain = f;
    string st; st.reserve(n);

    for (char ch : s) {
        int id = ch - 'a';
        remain[id]--;

        if (need[id] == 0) continue; // 不需要则跳过

        // 弹栈以变小，保持可行
        while (!st.empty() && st.back() > ch) {
            int tid = st.back() - 'a';
            if (remain[tid] >= need[tid] + 1) {
                st.pop_back();
                need[tid]++; // 被弹，后续还需一个
            } else break;
        }

        st.push_back(ch);
        need[id]--;
    }

    cout << st << "\n";
    return 0;
}

题目内容

这天，有人在小红书上发布了一道每日一题之编程题，如下:

给定一个长度为 $n$ 的字符串 $s$ ，该字符串仅由小写字母构成。 你需要删除尽可能少的字符，使得所得的字符串中,字符 ‘$a$’ 至 ‘$z$’ 的出现次数满足 ‘$a$’ 的次数≦‘$b$’的次数 $≦…≦‘z’$ 的次数.

显然，这个问题的答案非常多，因为可能有不同的删除方案。评论区已经有很多人给出了自己的解答。

为了展现你强大的编程实力，你决定写一个程序，在解决这个问题的同时，找到的字符串是全部答案中字典序最小的。直接输出这个字符串即可。

[名词解释]

不同长度字符串的字典序比较:从字符串的第一个字符开始逐个比较，直至发现第一个不同的位置，比较这个位置字符的字母表顺序，字母序更小的字符串字典序也更小;如果比较到其中一个字符串的结尾时依旧全部相同，则较短的字符串字典序更小。

输入描述

第一行输入一个整数 $n(1≤n≤2•10^5)$ ,表示字符串长度。

第二行输入一个长度为 $n$ ，仅由小写字母构成的字符串 $s$ 。除此之外，保证字符串至少包含一个 ‘$z$’ 。

输出描述

输出一个字符串，表示满足上述条件且字典序最小的结果字符串。

样例1

输入

4
xyxz

输出

xyz

说明

样例解释1

在这个样例中，删除第三个字符 '$x$ ’，得到" $xyz$ "，此时各字母出现次数均为 $1$ ，满足非严格递增，且为字典序最小。

样例2输入

3
azz

样例2输出

zz