Maximum weight transformation of a given string | Returns weight of the maximum weight transformation ; Base case ; If this subproblem is already solved ; Don 't make pair, so  weight gained is 1 ; If we can make pair ; If elements are dissimilar , weight gained is 4 ; if elements are similar so for making a pair we toggle any of them . Since toggle cost is 1 so overall weight gain becomes 3 ; save and return maximum of above cases ; Initializes lookup table and calls getMaxRec ( ) ; Create and initialize lookup table ; Call recursive function ; Driver Code
function getMaxRec ( str , i , n , lookup ) { if ( i >= n ) { return 0 ; } if ( lookup [ i ] != - 1 ) { return lookup [ i ] ; } let ans = 1 + getMaxRec ( str , i + 1 , n , lookup ) ; if ( i + 1 < n ) { if ( str [ i ] != str [ i + 1 ] ) { ans = Math . max ( 4 + getMaxRec ( str , i + 2 , n , lookup ) , ans ) ; } else { ans = Math . max ( 3 + getMaxRec ( str , i + 2 , n , lookup ) , ans ) ; } } return lookup [ i ] = ans ; } function getMaxWeight ( str ) { let n = str . length ; let lookup = new Array ( n ) ; lookup . fill ( 0 ) ; for ( let i = 0 ; i < n ; i ++ ) { lookup [ i ] = - 1 ; } return getMaxRec ( str , 0 , str . length , lookup ) ; } let str = " " ; document . write ( " " + " " + str + " " + getMaxWeight ( str ) ) ;