|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|10 초||512 MB||5||4||4||80.000%|
You are given a string s and an integer k. You can remove at most k non-intersecting substrings from s. Your task is to find the alphabetically (i.e., dictionary order) largest resulting string.
For example, with string abcdcada and k=2, you can choose the substrings [abc]d[ca]da and remove them to get dda.
Each input will begin with a line with a single integer c (1 ≤ c ≤ 2·105), which is the number of cases you must solve.
Each of the next c lines will contain an integer k and a string s (1 ≤ k ≤ |s| ≤ 105, s ∈ [a−z]*), separated by a space.
The total length of all strings in the input will be at most 106.
Output the largest string, alphabetically, that you can get by removing k or fewer non-intersecting substrings from s.
4 2 abcdcada 1 ababb 2 ababb 1 dadbdcdbdad
dda bb bbb ddcdbdad