Alex and his String

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.

Example:

Input:  s ="hackerearth", k = 3
Output: aceheakrhrt

Approach

C++

#include <bits/stdc++.h>
using namespace std;

string alexString(string s, int k)
{

    int n = s.size();
    string X = "";
    priority_queue<char, vector<char>, greater<char>> q;
    for (int i = 0; i < k; i++)
        q.push(s[i]);
    string res = "";
    for (int i = k; i < n; i++)
    {
        char c = q.top();
        q.pop();
        q.push(s[i]);
        res += c;
    }
    while (!q.empty())
    {
        char c = q.top();
        q.pop();
        res += c;
    }
    return res;
}
int main()
{

    string s = "hackerearth";

    int k = 3;

    cout << alexString(s, k) << "\n";

    return 0;
}

Python

import bisect
s="hackerearth"
n=len(s)
k=3
x=''
list1=sorted(s[:k])
x+=list1.pop(0)
for i in range(k,len(s)):
    bisect.insort(list1,s[i])
    x+=list1.pop(0)
x+=''.join(list1)
print(x)