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
using System ; 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 [ 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 ; } 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 str = " AAAAABB " ; Console . Write ( " Maximum ▁ weight ▁ of ▁ a " + " ▁ transformation ▁ of ▁ " + str + " ▁ is ▁ " + getMaxWeight ( str ) ) ; } }