You are given a string consisting of letters and the cost of adding a specific character to it. You need to convert the string into a pangram, i.e. it contains all the lower case alphabets (a-z) in it. The cost of above operation is to be minimised.
Subtask - 1
For this subtask, N = 1. This means the string contains only 1 lower case character. So, we would need to add all the remaining characters so that it becomes pangram. To minimise the cost, it is easy to see that we would add each character only once.
Subtask - 2
Similar to above solution, we would like to only add those characters which are missing in the substring so that it becomes a pangram. Also, each character should be added only once to minimise the cost.
Thus, we need to find efficiently which characters occur in the string and which do not. To do this, we just maintain an array, of size equal to the alphabet size (in this case 26), such that all of it’s value are initialised to 0. Now, we simply traverse the array from left to right and set the corresponding character to 1 in the array. Thus, at the end of the loop, we just need to find the location of 0 in the above array and add the corresponding cost of the character to the answer.
O(n + ALPHABET), where ALPHABET = number of lowercase characters (here 26)