HackerEarth Maximum subsequences problem solution

In this HackerEarth Maximum subsequences problem solution Consider a string s of length n that consists of lowercase Latin alphabetic characters. You are given an array A of size 26 showing the value for each alphabet. You must output the subsequence of size k whose sum of values is maximum.

If there are multiple subsequences available, then print the lexicographically smallest sequence. 

String p is lexicographically smaller than string q if p is a prefix of q and is not equal to q or there exists i, such that pi < qi and for all j < i it is satisfied that pj = aj. For example, ‘abc’ is lexicographically smaller than ‘abcd’, ‘abd’ is lexicographically smaller than ‘abec’, and ‘afa’ is not lexicographically smaller than ‘ab’.

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

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

#define     F           first
#define     S           second
#define     pb          push_back
#define     lb          lower_bound
#define     ub          upper_bound
#define     pii         pair<int,int>
#define     all(x)      x.begin(),x.end()
#define     fix         fixed<<setprecision(10)
#define     rep(i,a,b)  for(int i=int(a);i<=int(b);i++)
#define     repb(i,b,a) for(int i=int(b);i>=int(a);i--)
#define     FastIO      ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)

typedef double db;
typedef long long ll;

const int N=2e5+5;
const int mod=1e9+7;

string s;
vector<int>g[26];
int n,k,a[26],o[26];
bool comp(int i,int j){
    if(a[i]!=a[j]) return a[i]>a[j];
    return i<j;
}
void solve(){
    cin>>n>>k>>s;
    rep(i,0,25){
        cin>>a[i];
        o[i]=i;
        g[i].clear();
    }
    sort(o,o+26,comp);
    rep(i,1,n){
        int c=s[i-1]-'a';
        g[c].pb(i-1);
    }
    set<int>done;
    rep(i,0,25) rep(j,0,g[o[i]].size()-1){
        if(g[o[i]].size()-j<=k){
            k--;
            done.insert(g[o[i]][j]);
        }
        else if(k){
            auto it=done.lb(g[o[i]][j]);
            if(it!=done.end() and s[*it]-'a'>o[i]){
                k--;
                done.insert(g[o[i]][j]);
            }
        }
    }
    for(int i:done) cout<<s[i];
    cout<<'n';
}
signed main(){
    FastIO;
    int t;
    cin>>t;
    while(t--) solve();
    return 0;
}