Ninja and his girlfriend were getting married. Ninja’s father invited the ninja and his girlfriend to give blessings. Father has 2 blessings. Each blessing is in the form of a string consisting of lowercase characters(a-z) only.
But he can give only one blessing of ‘K’ length because some priest told him to do so. Thus he decides to generate a blessing using the other two blessings. While doing this, he wants to ensure that happiness brought into their life by his blessing is maximum.
The generated blessing is a common subsequence of length ‘K’ of the two blessings he has.
Happiness of the blessing he generates is calculated by the sum of ASCII values of characters in the blessing, and he wants the happiness to be maximum.
If he is not able to generate a common subsequence of length K, then the happiness is 0 (zero).
Ninja’s father comes to you and asks you to find the maximum happiness that can be generated by the two blessings he has.Example: l
Input: ‘BLESSING1’ = “asdf” ‘BLESSING2’ = “asdf” ‘K’ = 3 Output: 317 The optimal strategy would be To have the blessing as “sdf” which results in the total happiness of 115+100+102 = 317.
1 <= T <= 10 1 <= length(BLESSING1), length(BLESSING2) <= 100 Time Limit: 1 sec
Sample Output 1 :
2 asdf asdf 3 anandi jagya 3
Explanation Of Sample Input 1 :
Sample Input 2 :
For the first test case:- The optimal strategy would be To have the blessing as “sdf” which results in the total happiness of 115+100+102 = 317. For the second test case:- No common subsequence of length 3 is possible hence, the result is 0.
Sample Output 2 :
2 axyz yaxz 2 aaaaaazzzz zzzzaaaaaa 4