NINJA AND HAPPINESS

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 ).

The recursive approach discussed before can be optimized using memoization. We can memoize the result for each state with a particular ‘N’, ‘M’, and ‘K’, where ‘N’ and ‘M’ are the lengths of the strings.  In this way, we can save time from recalculating the already calculated results.
 

For memoization let us define a matrix 3-dimensional array ‘DP’ of size ‘N’ x ‘M’ x ‘K’.
 

DP[i][j][k] - Maximum happiness that can be obtained in the subproblem BLESSING1 [ i…N-1], BLESSING2 [ j…M-1] with the length of subsequence as ‘K’.

The steps are as follows:-

// Recursive function to find the maximum score

// Recursive function to find maximum happiness

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

[ int ] [ int ] [ int ] DP):

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. If ( DP [ i ] [ j ] [ K ] != -1 )
   • Return DP [ i ] [ j ] [ K ].
4. Initialise a variable ‘ANS’ as 0.
5. Update ‘ANS’ with the maximum of   getMaxHappiness ( BLESSING1, BLESSING2, i,    j - 1, k), getMaxHappiness ( BLESSING1, BLESSING2, i - 1, j, K ) .
6. 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 );
7. DP [ i ] [ j ] [ K ] = ‘ANS’.
8. Return ‘ANS’.

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

1. Initialize a  ‘DP’ matrix of size ( N + 1 ) * ( M + 1 ) * ( K + 1 ) with -1.
2. Return getMaxHappinessUtil ( BLESSING1, BLESSING2, N, M, K,  DP ).

The idea is the same as memoization. At every step, we have two choices either skip the character of the first string or the second string. We have one more additional choice if the current character of both of the strings is the same, in this choice, we take the current character in the matching subsequence and move ahead.

 In the end, we take the best of all the above choices.

DP[i][j][k] - Maximum happiness that can be obtained in the subproblem BLESSING1 [ i…N-1], BLESSING2 [ j…M-1] with the length of subsequence as ‘K’.

The steps are as follows:-

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

1. Build a 3-dimensional array ‘DP’ of size ( N + 1 ) * ( M + 1) * ( K +1 ).
2. Run a loop from i =0 to N:
   • Run a loop from  j= 0 to M:
     • Run a loop from k = 0 to K:
       • If( k == 0 ):

• DP [ i ] [ j ] [ k ] = 0.
• Continue
• If ( i == 0 OR j == 0 ):
  • DP [ i ] [ j ] [ k ] = - INFINITY      (a vey small value )
  • Continue
• DP [ i ] [ j ] [ k ] =  max ( DP [ i - 1] [ j ] [ k ] , DP [ i ] [ j - 1 ] [ k ]  )
• If ( BLESSING1 [ i -1  ] == BLESSING2 [ j - 1 ]:
  • DP [ i ] [ j ] [ k ] =  max ( DP [ i ] [ j ] [ k ] ,BLESSING1 [ i-1 ] +                                                                                             DP [ i - 1 ] [ j - 1 ] [ k ]  )

1. Return DP [ N ] [ M ] [ K ].