HackerEarth Maximum subsequences problem solution

YASH PAL, 31 July 202415 February 2026

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

coding problems solutions HackerEarth HackerEarth

Leave a Reply