Thursday Code Puzzler: Maximum Length Palindrome

Groovy code that assumes we have find biggest Palindrome among all the words in the string.

def biggestPalindrome(line) {
	line.tokenize().collect {it==it.reverse()?it.size():0 }.max()
}
assert biggestPalindrome("a aba abcba abcdef") == 5

Ruby/JRuby version. Just for fun, I added a "palindrome?" method to String. Also, this returns the largest palindrome, not just its size.

class String
  def palindrome?
    self == self.reverse
  end
end

def biggest_palindrome(str)
  str.split.select(&:palindrome?).sort_by(&:length).last
end

I think that what James asked is exactly the same of what you wrote here in more details and the other guys just misunderstood the problem. In particular James never wrote that the String is splitted in words and you have to find the longest word that is also a palindrome as the provided solutions seem to imply.

 Here's my java solution.

public class App {
    public static void main( String[] args ){
        getPalindrome("Madam steered the kayak like a racecar.");
    }
    
    public static String getPalindrome(String sentence){
        //remove punctuation
        sentence = sentence.replaceAll("(\\.)|(\\?)|(\\,)|(!)", "");
        String[] words = sentence.split("\\s");
        int wordLength = 0;
        int largestPalindromeLength = 0;
        String palindrome = null;
        for (String word : words) {
            word = word.toLowerCase();
            wordLength = word.length();
            char[] charArray = word.toCharArray();
            char[] yarrArach = new char[wordLength];
            //reverse it!
            for (int i = charArray.length; i > 0 ; i--) {
                yarrArach[wordLength - i] = charArray[i - 1];
            }
            boolean isPalindrome = false;
            for (int i = 0; i < wordLength; i++) {
                if(charArray[i] == yarrArach[i]){
                    isPalindrome = true;
                }else{
                    isPalindrome = false;
                    break;
                }
            }
            if(isPalindrome && wordLength > largestPalindromeLength){
                largestPalindromeLength = wordLength;
                palindrome = word;
            }
        }
        if (palindrome != null) {
            System.out.println("Largest Palindrome size: " + largestPalindromeLength + " Palindrome: " + palindrome);
            return palindrome;
        } else {
            System.out.println("No palindromes found in " + sentence);
        }
        return null;
    }
}

This is a piece of PHP code I wrote some time ago to find the longest substring that is a palindrome. It finds and displays the longest palindromes of odd length and even length independently.

I don't like very much how it is coded but it runs very fast and it uses a decent amount of memory.

$text = file_get_contents('http://en.wikipedia.org/wiki/Palindrome');


$msStart = microtime(TRUE);

$count = strlen($text);
$odd = array();
$even = array();
for ($i = 0; $i < $count; $i ++) {
  $odd[] = $i;
  $even[] = $i;
}
$foundOdd = TRUE;
$foundEven = TRUE;
$lenOdd = 0;
$lenEven = 0;
$paliOdd = $odd;
$paliEven = $even;
do {
  if ($foundOdd) {
    $odd = $paliOdd;
    $paliOdd = array();   // empty list

    $lenOdd ++;           // $len+1
    $foundOdd = FALSE;    // none found yet

    // try to extend each odd palindrome of length $len
    $nb = count($odd);
    for ($i = 0; $i < $nb; $i ++) {
      $pos = $odd[$i];
      if (isset($text[$pos-$lenOdd]) && isset($text[$pos+$lenOdd]) && $text[$pos-$lenOdd] == $text[$pos+$lenOdd]) {
        // found the center of a new palindrome of length $len
        $paliOdd[] = $pos;
        $foundOdd = TRUE;
      }
    }
  }

  if ($foundEven) {
    $even = $paliEven;
    $paliEven = array();

    $lenEven ++;
    $foundEven = FALSE;    // none found yet

    // try to extend each even palindrome of length $len
    $nb = count($even);
    for ($i = 0; $i < $nb; $i ++) {
      $pos = $even[$i];
      if (isset($text[$pos-$lenEven]) && isset($text[$pos+$lenEven-1]) && $text[$pos-$lenEven] == $text[$pos+$lenEven-1]) {
        // found the center of a new palindrome of length $len
        $paliEven[] = $pos;
        $foundEven = TRUE;
      }
    }
  }
} while ($foundOdd || $foundEven);
$lenOdd --;
$lenEven --;

$msTime = microtime(TRUE) - $msStart;


echo('Length of the input string: '.$count." bytes.\n\n");


// Display the list of found palindromes
echo("=== The longest palindromes having the length an odd number ===\n");
echo("Length=".(2*$lenOdd+1)."\n");
echo("Palindromes:\n");
foreach ($odd as $i)
  echo('offset '.$i.': '.substr($text, $i-$lenOdd, 2*$lenOdd+1)."\n");
echo("\n");

echo("=== The longest palindromes having the length an even number ===\n");
echo("Length=".(2*$lenEven)."\n");
echo("Palindromes:\n");
foreach ($even as $i)
  echo('offset '.$i.': '.substr($text, $i-$lenEven, 2*$lenEven)."\n");
echo("\n");

echo('Time: '.$msTime." sec.\n");
echo('Max memory used: '.(memory_get_peak_usage() / 1024 / 1024)." MB.\n");

Its output:

Length of the input string: 124022 bytes.

=== The longest palindromes having the length an odd number ===
Length=29
Palindromes:
offset 53964: atanoscillatemymetallicsonata
offset 54004: atanoscillatemymetallicsonata
offset 54057: atanoscillatemymetallicsonata

=== The longest palindromes having the length an even number ===
Length=24
Palindromes:
offset 73862: kuulilennuteetunneliluuk

Time: 0.39331603050232 sec.
Max memory used: 41.731117248535 MB.

Having a a second look at my code, I think there might be a considerable opportunity for further optimization, around line 40 (the call to isPalindrome). Basically, it has already been tester either this substring is a palindrome, at the previous round. So if the previous test did not resolve to a palindrome, then it is no use to test this substring. But this would require to deal with some exceptional cases (is the substring of odd or even length? was the substring interrupted because it got bellow the threshold of the length of the current longest palindrome?)

More simply, we may skip over any candidate whose length is longer than the length of the current longest palindrome plus two. This should make the algorithm much more efficient on very long inputs.

Also, in the main "for" loop, at line 17, we may change the stop condition to "i < chars.length() - longestPalindromeLength". Indeed, no longer palindrome will be found if there are not at least that much characters left.

    public static int biggestPalindrome(String input) {
        int maxLength = 0;
        int currentLength;
        String tokens[] = input.split("[ .?,]");
        for (String token : tokens)
        {    
	    if (token.length() > maxLength)
	    {	
                char[] chars=token.toLowerCase().toCharArray();
                currentLength = chars.length;
                for (int i=0; i< chars.length/2;i++) {
                    if (chars[i] != chars[chars.length-1-i]) {
                        currentLength = 0;
                    }
                }
                if (currentLength > maxLength) 
                   maxLength=currentLength;
                }
            }
        }      
        return maxLength;
    }