Palindromize
Time limit: 2000 ms
Memory limit: 65536 KB
Description
A palindrome is a string that reads the same from left to right as it does from right to left. Given a String s, return a palindrome that is produced by changing the minimum possible number of characters in s. Changing a character means replacing it with any single character at the same position. You are not allowed to remove or add any characters. If there are multiple answers, return the one that comes first alphabetically.
Input Format
One line consisting the string between 1 and 50 characters inclusively. Each character will be a lowercase letter ‘a’-‘z’.
Output Format
The palindromized string
Sample Input 1
ameba
Sample Output 1
abeba
Note
You can get “abeba” or “amema” with only 1 change. Among those two, “abeba” comes earlier alphabetically.
Sample Input 2
cigartragic
Sample Output 2
cigartragic
Note
The input is already a palindrome, so the best choice is to do 0 changes.
Sample Input 3
abcdef
Sample Output 3
abccba
Sample Input 4
cxbpaxz
Sample Output 4
cxapaxc
Solution
<pre>#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int main()
{
char text[100], alphabet[] = "abcdefghijklmnopqrstuvwxyz";
int begin, middle, end, length = 0, tempIndex1, tempIndex2;
char * pch;
int isPalindrome = 1,i= 0, a=0;
gets(text);
while (text[length] != '\0')
length++;
end = length - 1;
middle = length/2;
int temp[middle][2];
for (begin = 0; begin < middle; begin++){
if (text[begin] != text[end]){
temp[i][0] = begin;
temp[i][1] = end;
isPalindrome = 0;
i++;
}
end--;
}
if (isPalindrome){
printf("%s\n",text);
}
else{
for (a = 0; a < i; a++){
pch =strchr(alphabet, text[temp[a][0]]);
tempIndex1 = pch-alphabet;
pch =strchr(alphabet,text[temp[a][1]]);
tempIndex2 = pch-alphabet;
//printf("%d %d %d\n",temp[a][0], length/2, temp[a][1]);
if(tempIndex1 < tempIndex2){
text[temp[a][1]] = text[temp[a][0]];
}
else if(tempIndex1 > tempIndex2){
text[temp[a][0]] = text[temp[a][1]];
}
}
printf("%s\n",text);
}
return 0;
}</pre>