MYSTRING - Editorial

PROBLEM LINK:

Practice
Contest

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