PROBLEM LINK:
Author: Mohit Kadyan
Tester: Ankush Verma
DIFFICULTY:
EASY-MED
PREREQUISITES:
2 pointers,sorting
PROBLEM:
You are playing the piano on your PC using a new app in the market. You have to play the most beautiful melody given some conditions.
The app uses 26 buttons on the keyboard which are small alphabetical characters ‘a’ to ‘z’. All the letters are distinct.
You are given a sequence of values, the i-th element in the array adds a[i] value to the melody. To obtain the a[i] value you have to press the s[i] button on your keyboard.
Size of array a=size of string s=n
One more restriction is that you cannot press one button more than k times in a row else the button will break.
To get the final melody you have to press some buttons . You can skip any of them , however changing the initial order of the sequence is prohibited . The final melody will be judged based on the sum of the values used from the array a.
Basically , your task is to skip some buttons to get the most beautiful melody possible.
EXPLANATION:
Since we cannot press a button more than ‘k’ times consecutively, we need to select the ‘k’ maximum values whenever a button appears more than ‘k’ times in the string consecutively. Therefore we will store all the same buttons appearing together in the string and sort them in the descending order on the basis of their corresponding value in array ‘a’ and choose first k values.