NINJA AND HAPPINESS

Hard
0/120
Average time to solve is 45m
profile
Contributed by
0 upvote

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line consists of a number of test cases ‘T’.
The first line of each test case contains the string ‘BLESSING1’.
The second line of each test case contains the string ‘BLESSING2’.
The third line of each test case contains the length of common Subsequence 'K'.
Output format : 
The output consists of ‘T’ lines, each containing an integer that denotes the maximum happiness value the two blessings can generate.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10    
1 <= length(BLESSING1), length(BLESSING2) <= 100

Time Limit: 1 sec
Sample Input 1 :
2    
asdf
asdf
3
anandi
jagya
3
Sample Output 1 :
317
0
Explanation Of Sample Input 1 :
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 Input 2 :
2
axyz
yaxz
2
aaaaaazzzz
zzzzaaaaaa
4
Sample Output 2 :
243
488
Hint

Think of trying out all possible common subsequences of length K and choose the one which has the maximum happiness.

Approaches (3)
Recursion

In this approach, we will recursively try out all possible common subsequences of length K. A recursive function is called for every combination of the ending index of the two strings and the length of the common subsequence. Let’s say a common subsequence is ending with the ‘i’ index in ‘BLESSING1’ and with the ‘j’ index in ‘BLESSING2’ and the length of the required common subsequence is ‘k’. 


 

Our function returns the max value for a subsequence of length ‘k’ and ‘i’ and ‘j’ are a current index to ‘BLESSING1’ and ‘BLESSING2’. Thus we have 3 state variables. Now all you need to do is find the maximum value among all combinations of possible ‘i’, ‘j’, ’k’;



 

The steps are as follows:-

// Recursive function to find maximum happiness

function getMaxHappinessUtil ( String BLESSING1, String BLESSING2, int i,

                                                                 int j, int K ):

  1. If ‘K’ == 0 you already have K length subsequence
    • return 0.
  2. If the length of BLESSING1 or BLESSING2 == 0, this means you can’t go any further
    • return - INFINITY (a vey small value ).
  3. Initialise a variable ‘ANS’ as 0.
  4. Update ‘ANS’ with the maximum of   getMaxHappiness ( BLESSING1, BLESSING2, i, j - 1, k), getMaxHappiness ( BLESSING1, BLESSING2, i - 1, j, K ).
  5. If ( BLESSING1 [ i - 1 ] == BLESSING2 [ j - 1 ] ):
    • Update ‘ANS’ with the maximum of ‘ANS’ , ASCII value of       BLESSING1 [  i -1 ] +  getMaxHappiness( BLESSING1, BLESSING2, i -1 , j - 1, K -1 );
  6. Return ‘ANS’.

function getMaxHappiness(string BLESSING1, string BLESSING2, int N, int M,int K ):

  1. Return getMaxHappinessUtil ( BLESSING1, BLESSING2, N, M, K ).
Time Complexity

O( 3M+N ), Where ‘N’ is the length of string ‘BLESSING1’ and  ‘M’ is the length of the string ‘BLESSING2’. 

 

In the worst case recursion function will call 3 other recursive function each of which calls 3 other ones and it goes on and on till the sum of the length of both strings.

Space Complexity

O( N + M  ), Where ‘N’ is the length of string ‘BLESSING1’ and  ‘M’ is the length of the string ‘BLESSING2’. 
 

Extra auxiliary space will be needed for the recursion call stack.

 

Hence space complexity is O( N + M ).

Code Solution
(100% EXP penalty)
NINJA AND HAPPINESS
Full screen
Console