16 August 2014

Quiz 13: Find minimum number of steps to convert a string into palindrome

Problem:
A Palindrome is a string with is exactly same as its reverse string like abcba.
Given a string containing only alphabets from a-z, we have to find minimum number of steps required to convert the string to palindrome.
allowed operations:
- any alphabet can be reduced by 1 lower alphabet in a step like d can be reduced to c
- alphabet a cannot be reduced further

Sample Input:
abcd

Sample Output:
4

Explanations:- step1-> abcd -> abcc
                      step2->abcc->abcb
                      step3->abcb->abca
                      step4->abca->abba-> so 4 steps are required

Solution:

chomp($a=<STDIN>);   #take input
@arr=split("",$a);   #convert string to array  
$len = @arr;   #get length of array
$tmp = 0;      #this variable will store our count
for($i=0;$i<$len/2;$i++)
{
$a = ord($arr[$i]);   #ord will get ascii value
$b = ord($arr[$len-$i-1]);
if($a>$b)   #compare characters 
   {
   $tmp = $tmp + $a - $b;
   }
elsif($a<=$b)
   {
   $tmp = $tmp + $b - $a;
   }
}
print "$tmp";


Tips:
  • compare 1st and last character, then 2nd and last-2 and so on.

No comments:

Post a Comment