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>

 

Programming Problem Set #Palindromize
Tagged on:     

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.