Make largest palindrome by changing at most K | Java program to get largest palindrome changing atmost K digits ; Returns maximum possible palindrome using k changes ; Initialize l and r by leftmost and rightmost ends ; First try to make String palindrome ; Replace left and right character by maximum of both ; If k is negative then we can 't make  String palindrome ; At mid character , if K > 0 then change it to 9 ; If character at lth ( same as rth ) is less than 9 ; If none of them is changed in the previous loop then subtract 2 from K and convert both to 9 ; If one of them is changed in the previous loop then subtract 1 from K ( 1 more is subtracted already ) and make them 9 ; Driver code to test above methods
import java . text . ParseException ; class GFG { static String maximumPalinUsingKChanges ( String str , int k ) { char palin [ ] = str . toCharArray ( ) ; String ans = " " ; int l = 0 ; int r = str . length ( ) - 1 ; while ( l < r ) { if ( str . charAt ( l ) != str . charAt ( r ) ) { palin [ l ] = palin [ r ] = ( char ) Math . max ( str . charAt ( l ) , str . charAt ( r ) ) ; k -- ; } l ++ ; r -- ; } if ( k < 0 ) { return " Not ▁ possible " ; } l = 0 ; r = str . length ( ) - 1 ; while ( l <= r ) { if ( l == r ) { if ( k > 0 ) { palin [ l ] = '9' ; } } if ( palin [ l ] < '9' ) { if ( k >= 2 && palin [ l ] == str . charAt ( l ) && palin [ r ] == str . charAt ( r ) ) { k -= 2 ; palin [ l ] = palin [ r ] = '9' ; } else if ( k >= 1 && ( palin [ l ] != str . charAt ( l ) || palin [ r ] != str . charAt ( r ) ) ) { k -- ; palin [ l ] = palin [ r ] = '9' ; } } l ++ ; r -- ; } for ( int i = 0 ; i < palin . length ; i ++ ) ans += palin [ i ] ; return ans ; } public static void main ( String [ ] args ) throws ParseException { String str = "43435" ; int k = 3 ; System . out . println ( maximumPalinUsingKChanges ( str , k ) ) ; } }