Problem I
Cutting Strings

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\! \le \! c\! \le \! 2{\cdot }10^5$), 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\! \le \! k\! \le \! |s|\! \le \! 10^5, s\! \in \! [a{-}z]^*$), separated by a space.

The total length of all strings in the input will be at most $10^6$.


Output the largest string, alphabetically, that you can get by removing $k$ or fewer non-intersecting substrings from $s$.

Sample Input 1 Sample Output 1
2 abcdcada
1 ababb
2 ababb
1 dadbdcdbdad
CPU Time limit 5 seconds
Memory limit 1024 MB
Source North American Invitational Programming Contest (NAIPC) 2019
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in