All Tracks>Algorithms> String Algorithms> Basics of String Manipulation> Problem
Alex and his String
★★★★★

3.8

10 votes
Algorithms, Easy, Implementation, Priority queue, String Manipulation
Problem

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≤N≤105
  • 1≤K≤N
Sample Input
hackerearth
3
Sample Output
aceheakrhrt
Time Limit: 1
Memory Limit: 256
Source Limit:
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".

Contributers:
Editor Image

?