题解思路

本题要求我们从给定的字符串中删除 $m$ 个字符，得到剩余的字符串，并且使得这个剩余字符串的字典序最小。字典序的比较就是按字符的大小顺序来比较字符串，越小的字符越靠前。

问题分析

我们需要删除 $m$ 个字符，剩下的字符形成一个新的字符串。这要求我们保持剩余字符串的字典序最小。假设我们能选择某个字符删除，它是否对最终的字典序有影响呢？答案是有的，如果当前字符的字典序比后面的字符大，删除它可能会使得后面的字符能够更早地出现在结果字符串中，从而可能使字典序变得更小。

核心思想

我们可以通过贪心算法来解决这个问题。贪心算法的核心思想是每次从剩余字符中选择一个字典序最小的字符来加入结果中。

• 我们维护一个栈来存储当前选定的字符。
• 对于每个字符，如果当前字符小于栈顶的字符，并且栈的大小加上剩余的字符数大于等于 $n-m$（即剩余的字符数足够组成最终字符串的长度），那么就可以弹出栈顶字符。
• 继续这个过程，直到遍历完所有字符。

算法步骤

1. 设定一个栈，用来存放结果中的字符。
2. 遍历字符串中的每个字符：
   • 如果栈不为空，且当前字符小于栈顶字符，并且删除栈顶字符后剩余字符仍然足够形成一个长度为 $n-m$ 的字符串，弹出栈顶字符。
   • 将当前字符推入栈中。
3. 最终，栈中的字符即为字典序最小的结果字符串。

复杂度分析

• 对于每个字符，我们最多将其推入栈一次，并且最多弹出一次，所以时间复杂度为 $O(n)$，其中 $n$ 是字符串的长度。
• 总体时间复杂度是 $O(T \times n)$，其中 $T$ 是测试数据的个数。

Python代码实现

def min_lexicographical_string(n, m, s):
    stack = []
    # 遍历字符串中的每个字符
    for i in range(n):
        while stack and stack[-1] > s[i] and len(stack) + (n - i - 1) >= n - m:
            # 如果栈顶字符大于当前字符并且删除栈顶后还有足够的字符来构造最终结果
            stack.pop()
        # 将当前字符加入栈中
        stack.append(s[i])
    # 结果是栈中的前n-m个字符
    return ''.join(stack[:n - m])

# 输入处理
T = int(input())  # 测试组数
for _ in range(T):
    n, m = map(int, input().split())
    s = input().strip()
    # 输出最小字典序字符串
    print(min_lexicographical_string(n, m, s))

Java代码实现

import java.util.*;

public class Main {
    public static String minLexicographicalString(int n, int m, String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && stack.peek() > s.charAt(i) && stack.size() + (n - i - 1) >= n - m) {
                stack.pop();
            }
            stack.push(s.charAt(i));
        }
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < n - m; i++) {
            result.append(stack.get(i));
        }
        return result.toString();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 测试组数
        sc.nextLine();
        for (int t = 0; t < T; t++) {
            String[] nm = sc.nextLine().split(" ");
            int n = Integer.parseInt(nm[0]);
            int m = Integer.parseInt(nm[1]);
            String s = sc.nextLine();
            System.out.println(minLexicographicalString(n, m, s));
        }
        sc.close();
    }
}

C++代码实现

#include <iostream>
#include <stack>
#include <string>
using namespace std;

string minLexicographicalString(int n, int m, const string &s) {
    stack<char> stk;
    for (int i = 0; i < n; ++i) {
        while (!stk.empty() && stk.top() > s[i] && stk.size() + (n - i - 1) >= n - m) {
            stk.pop();
        }
        stk.push(s[i]);
    }
    string result = "";
    for (int i = 0; i < n - m; ++i) {
        result += stk.top();
        stk.pop();
    }
    return result;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        string s;
        cin >> s;
        cout << minLexicographicalString(n, m, s) << endl;
    }
    return 0;
}

题目内容

有一个长度为 $n$ 的字符串 $s$ ，你可以删除其中的 $m$ 个字符，使剩余字符串的字典序最小，输出这个字符串。

输入描述

第一行输入一个整数 $T$ ，代表接下来有 $T$ 组测试数据。

对于每一组测试数据，第一行输入两个数 $n,m$ 代表字符串的长度和可以删除的字符数量。

接下来输入长度为 $n$ 字符串。

$1≤T≤5$

$2≤n≤100000$

$1≤m＜n$

输出描述

对于每一组数据，输出一个答案。

样例1

输入

2
5 2
abcab
10 4
lkqijxsnny

输出

aab
ijsnny