Broken Dreams codechef solution- 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.

Broken Dreams solution codechef

SOLUTION – CLICK HERE

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.

Input Format 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.

Broken Dreams solution codechef 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.

Sample Input 1 

3
6 1
whizzy
14 2
aaacdecdebacde
4 3
dbca

Sample Output 1 Broken Dreams solution codechef

whizzy
aaaaccdecdebde
abcd

Explanation

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

SOLUTION – CLICK HERE

Leave a Comment

Your email address will not be published.