Find the minimum number of changes to make any substring of the given string a palindrome.
Difference between the length of the string and the count of maximum occurring character is the answer.
Any substring of a string can be a palindrome only if all characters are the same. The number of changes made can be minimized when all the characters of the string are converted to the maximum occurring character. Thus the count of maximum occurring character is to be found and subtracted from the length of the string to obtain the answer. The following pseudocode works by the above logic:
max=0 count for c in characters of given string: count[c % 'a']++ if( count[c % 'a'] > max ): max = count[c % 'a'] ans = len(string) - max
The above code maintains a list for the count of each character in the string and parallely finds the maximum of all such occurrences.
Can be found here.