Maximum weight transformation of a given string | C ++ program to find 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int getMaxRec ( string & str , int i , int n , int lookup [ ] ) { if ( i >= n ) return 0 ; if ( lookup [ i ] != -1 ) return lookup [ i ] ; int ans = 1 + getMaxRec ( str , i + 1 , n , lookup ) ; if ( i + 1 < n ) { if ( str [ i ] != str [ i + 1 ] ) ans = max ( 4 + getMaxRec ( str , i + 2 , n , lookup ) , ans ) ; else ans = max ( 3 + getMaxRec ( str , i + 2 , n , lookup ) , ans ) ; } return lookup [ i ] = ans ; } int getMaxWeight ( string str ) { int n = str . length ( ) ; int lookup [ n ] ; memset ( lookup , -1 , sizeof lookup ) ; return getMaxRec ( str , 0 , str . length ( ) , lookup ) ; } int main ( ) { string str = " AAAAABB " ; cout << " Maximum ▁ weight ▁ of ▁ a ▁ transformation ▁ of ▁ " << str << " ▁ is ▁ " << getMaxWeight ( str ) ; return 0 ; }