Make largest palindrome by changing at most K | Returns maximum possible palindrome using k changes ; Initialize l and r by leftmost and rightmost ends ; first try to make palindrome ; Replace left and right character by maximum of both ; If k is negative then we can 't make  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
def maximumPalinUsingKChanges ( strr , k ) : NEW_LINE INDENT palin = strr [ : : ] NEW_LINE l = 0 NEW_LINE r = len ( strr ) - 1 NEW_LINE while ( l <= r ) : NEW_LINE INDENT if ( strr [ l ] != strr [ r ] ) : NEW_LINE INDENT palin [ l ] = palin [ r ] = NEW_LINE INDENT max ( strr [ l ] , strr [ r ] ) NEW_LINE DEDENT k -= 1 NEW_LINE DEDENT l += 1 NEW_LINE r -= 1 NEW_LINE DEDENT if ( k < 0 ) : NEW_LINE INDENT return " Not ▁ possible " NEW_LINE DEDENT l = 0 NEW_LINE r = len ( strr ) - 1 NEW_LINE while ( l <= r ) : NEW_LINE INDENT if ( l == r ) : NEW_LINE INDENT if ( k > 0 ) : NEW_LINE INDENT palin [ l ] = '9' NEW_LINE DEDENT DEDENT if ( palin [ l ] < '9' ) : NEW_LINE INDENT if ( k >= 2 and palin [ l ] == strr [ l ] and palin [ r ] == strr [ r ] ) : NEW_LINE INDENT k -= 2 NEW_LINE palin [ l ] = palin [ r ] = '9' NEW_LINE DEDENT elif ( k >= 1 and ( palin [ l ] != strr [ l ] or palin [ r ] != strr [ r ] ) ) : NEW_LINE INDENT k -= 1 NEW_LINE palin [ l ] = palin [ r ] = '9' NEW_LINE DEDENT DEDENT l += 1 NEW_LINE r -= 1 NEW_LINE DEDENT return palin NEW_LINE DEDENT st = "43435" NEW_LINE strr = [ i for i in st ] NEW_LINE k = 3 NEW_LINE a = maximumPalinUsingKChanges ( strr , k ) NEW_LINE print ( " " . join ( a ) ) NEW_LINE