Puppy and Palindromes

A recent survey suggested that almost everybody knows that a palindrome is a string which reads the same backwards as forwards. More recently, puppy Tuzik invented a brand-new concept: K-palindromes. A string is called a K-palindrome if it is possible to make it a usual palindrome by replacing at most K characters. For example, a string abb can be made a palindrome by replacing one character, the