All Tracks Algorithms String Algorithms Basics of String Manipulation Problem

Alex and his String
/

Algorithms, Implementation, Priority queue, String Manipulation

Problem
Editorial
Analytics

Alex has a string S of length N consisting of lowercase alphabets. He wants to find lexicographically smallest string X of length N that can be formed using the following operation.

In one operation, he can select any one character among the at most first K characters of string S, remove it from string S and append it to string X. He can apply this operation as many times as he wants.

Help Alex find the string X.

Input format

  • The first line consists of a string of length N
  • The second line consists of an integer K.

Output format

  • Print the lexicographically minimum string that can be formed using the above operation.

Constraints

  • \(1 \le N \le 10^{5}\)
  • \(1 \le K \le N\)
SAMPLE INPUT
hackerearth
3
SAMPLE OUTPUT
aceheakrhrt
Explanation

First you can select 'a' from "hackerearth". Now the string X becomes "a" and string S becomes "hckerearth".

Now after applying the operation again, the string X becomes "ac" and the string S becomes "hkerearth".

Similarly after applying the operation n times, the string X becomes "aceheakrhrt".

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?