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


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';
}
}