题目大意
给定一个长度为 n 的小写字母串 s，考虑它的所有前缀 s[1..1], s[1..2], …, s[1..n]。
先把每个前缀内部的字符按字母表顺序排序（例如 “adcb” → “abcd”），得到 t₁, t₂, …, tₙ。
再对这 n 个字符串按字典序排序，求第 k 小的结果。
字典序比较时，从头比到尾，首个不同字符字母小者在前；如果一个串是另一个的前缀，则短串在前。

思路

1. 前缀字符计数

   • 用 cnt[i][d] 表示前缀 s[1..i] 中字母（‘a’+d）出现的次数。
   • cnt[0][*]=0；
   • i 从 1 到 n 时：复制 cnt[i]=cnt[i−1]，再让 cnt[i][ s[i]−'a' ]++。
   • 时间开销约为 26·n。

2. 自定义比较函数 cmp(i, j)（比较 tᵢ 和 tⱼ）

   • 从字母 d=0 到 25（对应 a…z）逐一比较 cnt[i][d] 和 cnt[j][d]：
     • 若不等，则有以下两种情况：
       1. cnt[i][d] > cnt[j][d]，说明 tᵢ 在此位置多了一个相同字母，字典序更靠前，返回 i 小于 j；
       2. cnt[i][d] < cnt[j][d]，说明 tᵢ 在这一轮就“跑完”了字母 d：
          • 如果 i == cnt[i][d]（前缀长度正好等于这个字母的出现次数），tᵢ 已结束，是短串，返回 i 小于 j；
          • 否则 tᵢ 后面还有更大的字母，字典序更靠后，返回 i 大于 j。
   • 如果所有字母次数都相同，则下标小的排在前。

3. 排序并取第 k 小

   • 构造 idx = [1,2,…,n]，用 cmp 作为比较器排序，时间约为 O(n log n × 26)。
   • 答案前缀下标 p = idx[k−1]。

4. 重建并输出 t_p

   • 按字母顺序把字符（‘a’+d）重复 cnt[p][d] 次拼接即可，耗时 O(26 + n)。

C++

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
        int n, k;
        string s;
        cin >> n >> k >> s;

        // 1) 构造前缀字符计数 cnt[i][d] 和每个前缀的最大字母索引 max_letter[i]
        vector<array<int,26>> cnt(n+1);
        vector<int> max_letter(n+1, -1);
        for(int d = 0; d < 26; ++d) cnt[0][d] = 0;
        for(int i = 1; i <= n; ++i){
            cnt[i] = cnt[i-1];
            int c = s[i-1] - 'a';
            cnt[i][c]++;
            max_letter[i] = max(max_letter[i-1], c);
        }

        // 2) 构造所有前缀的下标，并按自定义比较器排序
        vector<int> idx(n);
        iota(idx.begin(), idx.end(), 1);
        sort(idx.begin(), idx.end(), [&](int i, int j){
            // 比较排序后前缀 t_i 和 t_j 的字典序
            for(int d = 0; d < 26; ++d){
                int ci = cnt[i][d], cj = cnt[j][d];
                if(ci != cj){
                    if(ci > cj){
                        // 在字母 d 上 i 出现更多：此时 t_i[p]=d
                        // 如果 j 后面还有更大的字母，t_j[p]>d，则 d 更小 → t_i < t_j
                        if(max_letter[j] > d) return true;
                        // 否则 j 在此处结束成为短串，短串更小 → t_j < t_i
                        return false;
                    } else {
                        // ci < cj：在字母 d 上 i 比 j 少
                        // 如果 i 后面还有更大的字母，t_i[p]>d，则 t_i > t_j
                        if(max_letter[i] > d) return false;
                        // 否则 i 在此处结束成为短串，短串更小 → t_i < t_j
                        return true;
                    }
                }
            }
            // 如果所有字母次数都相同，则下标小的在前
            return i < j;
        });

        // 3) 取第 k 小的前缀下标
        int p = idx[k-1];

        // 4) 根据 cnt[p] 重建并输出 t_p
        string ans;
        ans.reserve(n);
        for(int d = 0; d < 26; ++d){
            ans.append(cnt[p][d], char('a' + d));
        }
        cout << ans << "\n";
    }

    return 0;
}

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(in.readLine());
        while (T-- > 0) {
            StringTokenizer tk = new StringTokenizer(in.readLine());
            int n = Integer.parseInt(tk.nextToken());
            int k = Integer.parseInt(tk.nextToken());
            String s = in.readLine().trim();

            // 1) 构造前缀字符计数 cnt[i][d] 和每个前缀的最大字母索引 maxLetter[i]
            int[][] cnt = new int[n+1][26];
            int[] maxLetter = new int[n+1];
            Arrays.fill(maxLetter, -1);
            for (int i = 1; i <= n; i++) {
                System.arraycopy(cnt[i-1], 0, cnt[i], 0, 26);
                int c = s.charAt(i-1) - 'a';
                cnt[i][c]++;
                maxLetter[i] = Math.max(maxLetter[i-1], c);
            }

            // 2) 构造下标数组并排序
            Integer[] idx = new Integer[n];
            for (int i = 0; i < n; i++) idx[i] = i + 1;
            Arrays.sort(idx, (i, j) -> {
                // 比较 t_i 和 t_j
                for (int d = 0; d < 26; d++) {
                    int ci = cnt[i][d], cj = cnt[j][d];
                    if (ci != cj) {
                        if (ci > cj) {
                            // i 在 d 上更多：若 j 后面有更大的字母，t_i < t_j
                            if (maxLetter[j] > d) return -1;
                            // 否则 t_j 是短串更小，t_i > t_j
                            return 1;
                        } else {
                            // ci < cj：若 i 后面有更大字母，t_i > t_j
                            if (maxLetter[i] > d) return 1;
                            // 否则 t_i 是短串更小
                            return -1;
                        }
                    }
                }
                // 完全相同时，下标小者在前
                return Integer.compare(i, j);
            });

            // 3) 第 k 小的前缀下标
            int p = idx[k-1];

            // 4) 重建并输出 t_p
            StringBuilder sb = new StringBuilder();
            for (int d = 0; d < 26; d++) {
                for (int t = 0; t < cnt[p][d]; t++) {
                    sb.append((char)('a' + d));
                }
            }
            System.out.println(sb);
        }
    }
}

Python

import sys
import threading
from functools import cmp_to_key

def main():
    input = sys.stdin.readline
    T = int(input())
    for _ in range(T):
        n, k = map(int, input().split())
        s = input().strip()
        
        # 1) 构造前缀字符计数 cnt 和每个前缀的最大字母索引 max_letter
        cnt = [[0]*26 for _ in range(n+1)]
        max_letter = [-1]*(n+1)
        for i, ch in enumerate(s, start=1):
            c = ord(ch) - ord('a')
            cnt[i] = cnt[i-1].copy()
            cnt[i][c] += 1
            max_letter[i] = max(max_letter[i-1], c)
        
        # 2) 自定义比较函数
        #    比较排序后前缀 t_i 和 t_j 的字典序
        def cmp(i, j):
            for d in range(26):
                ci, cj = cnt[i][d], cnt[j][d]
                if ci != cj:
                    if ci > cj:
                        # 第一个不同字母是 d 且 ci>cj：
                        # 若前缀 j 中存在更大的字母 (max_letter[j]>d)，
                        # 则 t_i[p]=d < t_j[p]>d → t_i < t_j
                        # 否则 t_j 在 p 位置跑完了，t_j 短串 → t_j < t_i
                        return -1 if max_letter[j] > d else 1
                    else:
                        # ci < cj，同理：
                        # 若前缀 i 中存在更大的字母 (max_letter[i]>d)，
                        # 则 t_j[p]=d < t_i[p]>d → t_i > t_j
                        # 否则 t_i 在 p 位置跑完了，t_i 短串 → t_i < t_j
                        return 1 if max_letter[i] > d else -1
            # 完全相同时，下标小的在前
            return -1 if i < j else (1 if i > j else 0)
        
        # 3) 排序并取第 k 小
        idx = list(range(1, n+1))
        idx.sort(key=cmp_to_key(cmp))
        p = idx[k-1]
        
        # 4) 生成并输出排好序的前缀 t_p
        out = []
        for d in range(26):
            if cnt[p][d]:
                out.append(chr(ord('a')+d) * cnt[p][d])
        print(''.join(out))

if __name__ == "__main__":
    threading.Thread(target=main).start()

题目内容

小红拿到一个长度为 $n$ 的字符串 $s$，对于 $s$ ，共有 $n$ 个前缀字符串，例如：$s="adcb"$ ，那么 $s$ 的前缀字符串依次为 {$"a","ad","adc","adcb"$}，现在小红会对这 $n$ 个字符串先在其内部按照字母表顺序从小到大的排序规则先排好，为 {$"a","ad","acd","abcd"$} 。然后再对 $n$ 个字符串按照字典序从小到大的排序规则排好，为 {$“a",“abcd",“acd","ad"$}

小红想知道最后排好集合中第 $k$ 小的字符串。

从字符串的第一个字符开始逐个比较，直到找到第一个不同的位置，通过比较这个位置字符的字母表顺序得出字符串的大小，称为字典序比较。如果比较到其中一个字符串的结尾时依旧相同，则较短的字符串较小。

输入描述

第一行一个整数 $T(1 ≤T ≤ 100)$ ，表示单个测试文件的期据组数。

对于每组数据的格式为：

第一行两个整数 $n,k(1≤n≤2×10^5,1≤k≤n)$ ，表示字符串长度和所求字符串的排名。

第二行一个长度为 $n$ 的字符串 $s$，保证仅由小写字母组成。

数据保证 $n$ 之和小于等于 $2×10^5$ 。

输出描述

对于每组数据，输出一个字符串，为排序后得到的第 $k$ 小字符串。

样例1

输入

2
4 2
adcb
1 1
a

输出

abcd
a