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 ; 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
def getMaxRec ( string , i , n , lookup ) : NEW_LINE INDENT if i >= n : NEW_LINE INDENT return 0 NEW_LINE DEDENT if lookup [ i ] != - 1 : NEW_LINE INDENT return lookup [ i ] NEW_LINE DEDENT ans = 1 + getMaxRec ( string , i + 1 , n , lookup ) NEW_LINE if i + 1 < n : NEW_LINE INDENT if string [ i ] != string [ i + 1 ] : NEW_LINE INDENT ans = max ( 4 + getMaxRec ( string , i + 2 , n , lookup ) , ans ) NEW_LINE DEDENT else : NEW_LINE INDENT ans = max ( 3 + getMaxRec ( string , i + 2 , n , lookup ) , ans ) NEW_LINE DEDENT DEDENT lookup [ i ] = ans NEW_LINE return ans NEW_LINE DEDENT def getMaxWeight ( string ) : NEW_LINE INDENT n = len ( string ) NEW_LINE lookup = [ - 1 ] * ( n ) NEW_LINE return getMaxRec ( string , 0 , len ( string ) , lookup ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT string = " AAAAABB " NEW_LINE print ( " Maximum ▁ weight ▁ of ▁ a ▁ transformation ▁ of " , string , " is " , getMaxWeight ( string ) ) NEW_LINE DEDENT