# 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'.

## HackerEarth Maximum subsequences problem solution.

`#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;}`

### Second solution

`#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 5e5 + 14, z = 26;int main(){    ios::sync_with_stdio(0), cin.tie(0);    int t;    cin >> t;    while(t--){        int n, k;        string s;        cin >> n >> k >> s;        int value[z], per[z], need[z] = {};        vector<int> have[z];        for(int i = 0; i < n; i++)            have[s[i] - 'a'].push_back(i);        for(int i = 0; i < z; i++)            cin >> value[i];        iota(per, per + z, 0);        sort(per, per + z, [&](int i, int j){  return value[i] != value[j] ? value[i] > value[j] : i < j;  });        set<int> picked;        for_each(per, per + z, [&](int i){            for(int j = 0; j < have[i].size(); j++)                if(have[i].size() - j <= k || k && s[*picked.lower_bound(have[i][j])] - 'a' > i)                    picked.insert(have[i][j]), k--;        });        for(auto i : picked)            cout << s[i];        cout << '\n';    }}`