# [Solution] Broken Dreams solution codechef

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 SS′ 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 SS′ as the concatenation of these subsequences, i.e, S=S1+S2++SKS′=S1+S2+…+SK, where ++ denotes string concatenation.

Determine the lexicographically smallest SS′ 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 SS′ that can be created.

### Constraints

• 1T10001≤T≤1000
• 1N1051≤N≤105
• 1KN1≤K≤N
• SS contains only lowercase Latin letters.
• Sum of NN over all cases won’t exceed 21052⋅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=aS2=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 SS′.