Ray And Strings :
Difficulty Level : Easy
Submissions : 382
Asked In :
Marks :10
: 3 | : 0
Ray is playing with strings and he came up with a very weird question.
He gave you string $$$str$$$ of size $$$N$$$ having lowercase English alphabets and an array $$$a$$$ of size $$$N$$$ which contains $$$N$$$ non-negative integer value for every character in the string $$$str$$$.
Your task is to delete characters from the string following the given instructions.
Delete exactly one occurence of every character present in the string.
for e.g. str="aabba" and array is $$$[2,3,1,2,3]]$$$ so frequency of $$$'a'$$$ is 3 and $$$'b'$$$ is 2 let's say you deleted 0th index i.e $$$'a'$$$ and 2nd index i.e $$$'b'$$$ resulting in updated array as $$$[0,3,0,2,3]$$$.
Note here
1.Deletion means updating value of character as $$$0$$$ . You have to delete the characters in such a manner after all deletions remaining sum is minimum.
2.The value of every undeleted character remains same.
The first line contain $$$1 \le T \le 10$$$ number of test cases.
For every test case.
- The first line contains $$$ 1\le N \le 10^{5}$$$ i.e size of the string.
- The second line contains a string consisting of lowercase English alphabets of size $$$N$$$ where $$$'a' \le str[i] \le 'z'$$$ where $$$(0\le i <n)$$$
- The third line contains array $$$value$$$ of $$$N$$$ space separated non negative integer $$$(0\le value_i \le10^{9})$$$ value as mentioned in the question.
For every test case output the minimum sum of the array you get in a new line.
25aabba2 3 1 2 36aaabbb5 7 2 4 8 10
6 19
You have to delete exactly one occurence of every character in the string.
In first test case it would be optimal to remove(0-based indexing) 1st character i.e $$$'a'$$$ and 3rd character i.e $$$'b'$$$ resulting array would be $$$[2,0,1,0,3]$$$ . which has minimum sum = $$$6$$$.
