PROBLEM LINK:
Author: Bhavik Jain
Tester: Satyam
Editorialist: Bhavik Jain
DIFFICULTY:
EASY
PREREQUISITES:
Greedy, Sorting
PROBLEM:
Given a string S (consisting of upper-case alphabets only) whose cost C is defined as sum of positions of all the characters of S as they appear in reversed-alphabetical order and a integer p (p<C), find the maximum number of characters that can be removed from S such that the final cost of S remains greater than p.
EXPLANATION:
Let’s find the maximum number of characters that can be removed according to the given condition.
First we will sort the given string S in reverse order.
Next we will find the cost C of the string by adding the values of each alphabet in S. The values are : { ‘A’ : 26, ‘B’ : 25, ‘C’ : 24, . . . ,‘X’ : 3, ‘Y’ : 2, ‘Z’ : 1}
count = 0
Let v be the value of first alphabet of S
while C - v > p:
- count++
- Decrease C by v
- Update v to the value of next alphabet in S
The code is given below.
Time Complexity:
O(N logN) per test case.
SOLUTIONS:
Setter's Solution (Python)
t=int(input())
while t:
n,p=map(int,input().split())
s=input()
s=sorted(s, reverse=True)
c=0
for j in s:
c+=ord("Z")-ord(j)+1
ans,j=0,0
v=(ord("Z")-ord(s[j])+1)
while (c-v)>p:
ans+=1
j+=1
c-=v
if j<n:
v=(ord("Z")-ord(s[j])+1)
else:
break
print(ans)
t-=1
Tester's Solution (C++)
#include <bits/stdc++.h>
using namespace std;
#define l long long
int main()
{
l t; cin>>t;
while(t--){
l n,p,f=0; cin>>n>>p;
vector<l> a;
while(n--){
char c; cin>>c;
a.push_back('Z'-c+1);
}
sort(a.rbegin(),a.rend());
for(auto i:a){
if(p<0){
f++;
}
else{
p-=i;
}
}
cout<<f<<"\n";
}
}