Consider a string \(s\) of length \(n\) that consists of lowercase Latin alphabetic characters. You are given an array \(A\) of size 26 showing the value for each alphabet. You must output the subsequence of size \(k\) whose sum of values is maximum.
If there are multiple subsequences available, then print the lexicographically smallest sequence.
String \(p\) is lexicographically smaller than string \(q\) if \(p\) is a prefix of \(q\) and is not equal to \(q\) or there exists \(i\), such that \(p_i < q_i\) and for all \(j < i\) it is satisfied that \(p_j = q_j\). For example, '\(abc\)' is lexicographically smaller than '\(abcd\)', '\(abd\)' is lexicographically smaller than '\(abec\)', and '\(afa\)' is not lexicographically smaller than '\(ab\)'.
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.
Output format
Print a string for each test case.
Constraints
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" is lexicographically smaller that "caa".
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" is lexicographically smaller that "acabc".
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor