You have to make a word dictionary for NLP study. A string is given to you of length n that consists of lowercase alphabets. An array of size 26 is also given to show the numeric value for each alphabet. You should display the subsequence of a particular size whose sum of values is maximum. If multiple subsequences are available, then print the subsequence which would come earlier in any normal dictionary. Input format The first line contains an integer t representing the number of test cases. For each test case, you are given two integers n and k, a string s, and an array A of length 26. n=number of characters in string, k=the size of the desired subsequence Output format Print a string for each test case. Explanation: In the first test case, optimal way is to include 'a' character twice and 'c' character once, so that the obtained sum (5+5+3=13) is maximum. Only two subsequences ("caa" and "aca") are there with sum 13, but "aca" would come before "caa" in dictionary. In the second test case, optimal way is to include 'a' character twice, 'c' character twice and 'b' character once, so that the obtained sum (100+100+80+80+50=410) is maximum. Only two subsequences ("abcac" and "acabc") are there with sum 410, but "abcac" would come before "acabc" in dictionary.
You have to make a word dictionary for NLP study. A string is given to you of length n that consists of lowercase alphabets. An array of size 26 is also given to show the numeric value for each alphabet. You should display the subsequence of a particular size whose sum of values is maximum. If multiple subsequences are available, then print the subsequence which would come earlier in any normal dictionary.
Input format
The first line contains an integer t representing the number of test cases.
For each test case, you are given two integers n and k, a string s, and an array A of length 26. n=number of characters in string, k=the size of the desired subsequence
Output format
Print a string for each test case.
Explanation:
In the first test case, optimal way is to include 'a' character twice and 'c' character once, so that the obtained sum (5+5+3=13) is maximum. Only two subsequences ("caa" and "aca") are there with sum 13, but "aca" would come before "caa" in dictionary.
In the second test case, optimal way is to include 'a' character twice, 'c' character twice and 'b' character once, so that the obtained sum (100+100+80+80+50=410) is maximum. Only two subsequences ("abcac" and "acabc") are there with sum 410, but "abcac" would come before "acabc" in dictionary.
Step by step
Solved in 3 steps with 1 images
