I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Maximum Length Palindrome

02.07.2013
| 4611 views |
  • submit to reddit

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Do you have code puzzlers that you'd like to share with the DZone community?  If so, please submit here. 

Find the Maximum Length Palindrome in a String

Provide a method that takes a string and returns the maximum length palindrome. A palindrome  is a word, phrase or number that can be read the same in either direction.

Catch up on all our previous puzzlers here.

 

Comments

Vijay Nathani replied on Thu, 2013/02/07 - 4:49am

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

Chakik Nazim replied on Fri, 2013/02/08 - 4:34pm

scala versions


def biggestPalindrome(s:String)=s.split(" ").filter(t => t==t.reverse).maxBy(p=>p.size).size

def biggestPalindrome2(s:String)=s.split(" ").filter(s=>s==s.reverse).map(_.length).max

Mark Thomas replied on Mon, 2013/02/11 - 7:42am

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

sun east replied on Fri, 2013/02/08 - 8:38pm

This problem is not so fun. Here is an alternate one more interesting:
For a given string, find the maximum length palindrome which is a subsequence of the string.
Note: we call xs is a subsequence of s = s(0)s(1)s(2)...s(n-1) if there exists 0<= i0 < i1 <...<ik-1 < n such that     xs(0) = s(i0), xs(1) = s(i1) ,...,xs(k-1) = s(ik-1)

example:
s = "ababa1111ba"
xs = "ab1111ba"

s = "1234234234"
xs = "23432"

Mario Fusco replied on Wed, 2013/02/13 - 8:45am in response to: sun east

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.

Aaron Sawyer replied on Wed, 2013/02/13 - 10:23am in response to: sun east

 line 5, s has no palindrome subsequence/substring. Perhaps a typo?

s = "1234324324"

might make line 6 correct.

Steven Dunst replied on Wed, 2013/02/13 - 10:37am

 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;
    }
}

James Sugrue replied on Wed, 2013/02/13 - 11:08am in response to: Mario Fusco

You're right Mario - I'll update the question to make this more clear..

Valentin Valciu replied on Wed, 2013/02/13 - 12:27pm

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.


James Watkins-Harvey replied on Wed, 2013/02/13 - 1:08pm

I can think of two main approach to solve the "longest palindrome substring" problem in reasonable time: either iteratively consider each character as the center (or first character of the center) of a palindrome, and then walk outward until that palindrome can't be expended more, or form a chain from identical letters to the next one, in order to speed up search for palindrome candidates, then test candidates until the length of the candidate get bellow the current maximum length. I have not deeply analyzed the exact performance of each approach, but the second one sounds more thrilling, so here it is, as draft Java code (untested, run at your own risk).

Note that I deliberately chose to receive the input as an array of byte, rather than a regular String, because I don't want to deal with character normalization (lowercase/uppercase/accentuated characters/ligatures and other oddities that are usually not considered when comparing characters of a palindrome). It is also very convenient that the range of possible characters be as small as possible, since I use this length to build up the index, though a wider range of possible characters would make this approach only slightly harder to implement.

public byte[] findLongetPalindrome(byte[] chars) {

    // We assume a palindrome must have a length of at least two chars;
    // otherwise, any single char would be a palindrome by itself.
    if (chars.length < 2)
        return null;

    int longestPalindromeLength = 1;
    int longestPalindromePos = 0;

    int[] firstOccurence = new int[256][];
    int[] nextOccurence = new int[chars.length()];
    int[] lastOccurence = new int[256][];

    Arrays.fill(firstOccurence, -1);

    for (int i = 0 ; i < chars.length() ; i++) {
        byte c = chars[i];
    
        if (firstOccurence[c] == -1) {
            // This is a first occurence. There is no chance that this char
            // be part of a palindrome (that is, of length > 1).

            firstOccurence[c] = i;
            lastOccurence[c] = i;

        } else {
            // This is a recurring occurence. First make the chain.
            nextOccurence[lastOccurence[c]] = i;
            lastOccurence[c] = i;

            // Now walk the chain from the start, and check for palindromes
            int pos = firstOccurence[i];
        
            // We can stop walking the chain as soon as the length of the
            // substring get shorter than the longest palindrome
            while ( (i - pos + 1) > longestPalindromeLength) {
                // Note that we already know that chars[pos]==chars[i], so
                // can reduce the check for palindromes from pos+1 to i-1
                if (isPalindrome(chars, pos + 1, i)) {
                    longestPalindromeLength = (i - pos + 1);
                    longestPalindromePos = pos;

                    break;
                }

                pos = nextOccurence[pos];
            }
        }
    }

    if (longestPalindromLength == 1)
        return null;

    return Arrays.copyOf(chars,longestPalindromePos,longestPalindromeLength);
}


boolean isPalindrome(byte[] chars, int start, int end) {
    while (start < end - 1) {
        if (chars[start] != chars[end])
            return false;

        start++;
        end++;
    }

    return true;
}

James Watkins-Harvey replied on Wed, 2013/02/13 - 1:23pm in response to: James Watkins-Harvey

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.

Daniel Sobral replied on Wed, 2013/02/13 - 1:44pm

Once you finished, you might want to look at this article  for a tour-de-force on really efficient longest palindrome algorithm.

Chris Menard replied on Wed, 2013/02/13 - 2:56pm

    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;
    }


Chris Menard replied on Wed, 2013/02/13 - 2:57pm in response to: Chris Menard

 Added token.lenght() test after I read James' last comments

Camilo Rivera replied on Thu, 2013/11/07 - 6:33pm

Ruby code . Some performance enhancements product of not relying on Ruby's magical iterative utility methods.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.