21 August 2014

Quiz 16: Find if a string can be converted to palindrome or not

Problem:
There is a string having lower case english alphabets only. Find out if the string can be changed into palindrome by rearranging alphabets.

Constraints
1<=length of string<=100000
String contains only lower case english language alphabets

Sample Input
poiuytrecwkqgqlpowieurytaaaxxckla

Sample Output:
poiuytrecwkqgqlpowieurytaaaxxckla can be converted to palindrome

Explanations:-
String can be changed to "poiuytrecwkqlaaxgxaalqkwrectyuiop" which is a palindrome

Solution:

chomp($a =<STDIN>);
@output;
$odd=0;
@arr = split("",$a);
@arr = sort(@arr);
$len = @arr;
if($len<1 or $len > 100000)
   {
   exit;
   }
foreach(@arr)
{
$ascii = ord($_);
if($ascii<97 or $ascii > 122)
   {
   exit;
   }
}
my $tmp = 1;
for(my $i=0;$i<@arr;$i++)
  {
  if($arr[$i] eq $arr[$i+1])
       {
       $tmp++;
       }
   else{ 
       push(@output,$tmp);
       $tmp = 1;
       }
   }
for(my $j=0;$j<@output;$j++)
{
if($output[$j] % 2 == 0)
   {
   }
   else
   {
   $odd++;
   }
if($odd > 1)
{
print "$a cannot be converted to palindrome";
exit;
}
}
print "$a can be converted to palindrome";



Tips:
Each alphabet should occur even number of times, only 1 alphabet can occur odd number of times which can be in middle of string.

No comments:

Post a Comment