[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′.

For Solution

Click here

Leave a Comment