CWA1705 - Editorial

PROBLEM LINK:

Problem
Contest

Author: Bernett Orlando
Editorialist: Sowmiya Nagarajan

DIFFICULTY:

Easy

PROBLEM:

Find the minimum number of changes to make any substring of the given string a palindrome.

QUICK EXPLANATION:

Difference between the length of the string and the count of maximum occurring character is the answer.

EXPLANATION:

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[26]
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.

AUTHOR’S SOLUTION:

Can be found here.

1 Like