Maximum weight transformation of a given string | Java 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
class GFG { static 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 . charAt ( i ) != str . charAt ( 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 ; } static int getMaxWeight ( String str ) { int n = str . length ( ) ; int [ ] lookup = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { lookup [ i ] = - 1 ; } return getMaxRec ( str , 0 , str . length ( ) , lookup ) ; } public static void main ( String [ ] args ) { String str = " AAAAABB " ; System . out . println ( " Maximum ▁ weight ▁ of ▁ a " + " ▁ transformation ▁ of ▁ " + str + " ▁ is ▁ " + getMaxWeight ( str ) ) ; } }