Broken Dreams solution codechef – You are given a string SS of length NN, containing lowercase Latin letters. You are also given an integer KK.

You would like to create a new string S′S′ by following the following process:

• First, partition SS into exactly KK non-empty subsequences S1,S2,…,SKS1,S2,…,SK. Note that every character of SS must be present in exactly one of the SiSi.
• Then, create S′S′ as the concatenation of these subsequences, i.e, S′=S1+S2+…+SKS′=S1+S2+…+SK, where ++ denotes string concatenation.

Determine the lexicographically smallest S′S′ that can be created.

Broken Dreams solution codechef

• The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains two space-separated integers, NN and KK.
• The second line of each test case contains the string SS.

Output Format

For each test case, output on a new line the lexicographically smallest string S′S′ that can be created.

Constraints

• 1≤T≤10001≤T≤1000
• 1≤N≤1051≤N≤105
• 1≤K≤N1≤K≤N
• SS contains only lowercase Latin letters.
• Sum of NN over all cases won’t exceed 2⋅1052⋅105.

Broken Dreams solution codechef

 

3
6 1
whizzy
14 2
aaacdecdebacde
4 3
dbca

Sample Output 1 

whizzy
aaaaccdecdebde
abcd

Broken Dreams solution codechef

Test Case 11: K=1K=1, so our only option is to set S′=S1=whizzyS′=S1=whizzy.

Test Case 22: Partition S=aaacdecdebacdeS=aaacdecdebacde into S1=aaaacS1=aaaac and S2=cdecdebdeS2=cdecdebde, to form S′=aaaaccdecdebdeS′=aaaaccdecdebde.

Test Case 33: Partition S=dbcaS=dbca into S1=aS1=a, S2=bcS2=bc, and S3=dS3=d to form S′=abcdS′=abcd.

In both test cases 22 and 33, it can be shown that no other partition gives a lexicographically smaller S′S′.

For Solution

“Click here“