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