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)
Yes, you can do that, but in your case you are assigning particular index (26) to 0, which could have also lead to runtime error as size of array you declared is also 26. I have modified the code, which can can see here. Btw, i would suggest you to use memset or fill in C++.
I’m getting a weird problem with this problem. The same program, when the strings,vectors are defined as global outside any function, I get wrong answer but when I put them inside the main() function I get correct answer.
Just put outside main function and you get WA. HOW AND WHY?