## Find The Longest Palindrome In A String

### October 15, 2010

Greplin issued a programming challenge recently that required programmers to solve three problems; when completed, Greplin issued an invitation to send them a resume. The first problem required the programmer to find the longest palindrome in the following 1169-character string:

Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta

inentanewnationconceivedinzLibertyanddedicatedtotheproposit

ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa

rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic

atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh

avecometodedicpateaportionofthatfieldasafinalrestingplacefo

rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog

etherfangandproperthatweshoulddothisButinalargersensewecann

otdedicatewecannotconsecratewecannothallowthisgroundThebrav

elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove

ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl

ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI

tisforusthelivingrathertobededicatedheretotheulnfinishedwor

kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather

forustobeherededicatedtothegreattdafskremainingbeforeusthat

fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh

ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres

olvethatthesedeadshallnothavediedinvainthatthisnationunsder

Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb

ythepeopleforthepeopleshallnotperishfromtheearth

Your task is to write a function that finds the longest palindrome in a string and apply it to the string given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Could someone delete my previous comment please ?

I tried the naive way. I don’t know much about palindrome.

oops my pastebin does not show up. my solution

[…] today’s Programming Praxis exercise, our goal is to write an alogrithm to find the longest palindrome in a […]

My Haskell solution (see http://bonsaicode.wordpress.com/2010/10/15/programming-praxis-find-the-longest-palindrome-in-a-string/ for a version with comments):

Remco: I also used the O(n^3) algorithm when I solved the challenge; I wrote the code as fast as I can type, it worked the first time, and once I had the answer I moved on to the second level. But after I finished the challenge I went looking for a better way, and Jeuring’s solution was so pretty I had to include it in an exercise.

By the way, the second level was easy, involving fibonacci numbers, prime checking and integer factorization; I could have stolen code from several of our earlier exercises to solve it quickly, but instead I looked up the prime fibonacci numbers on OEIS and used Dario Alpern’s applet for the factorization. The third level involved generating all possible subsets and testing them for a particular condition, and the brute-force solution took over a minute to run. I’ve since got a much better solution for the third level, but I’m still looking for the “perfect” solution that I can use for an exercise.

Phil

My solution in Python:

I took the greplin challenge a few days ago too. Here was

my solution to problem 1. It’s O(n**2) in the worst case

but much closer to O(n) for typical input data.

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

longest_palindrome.rb

hosted with ❤ by GitHub

I also did the slow and steady method. O(n^3) isn’t bad for 1169 characters, but it won’t be great for larger data. Small speed up: in my flp() function, starting case is a single character, so we begin by only searching for palindromes of length 2 or greater.

And here’s my go at the O(n^2) solution described in the post, in Ruby:

Hurray for leaving debugging code in the post >.<

txt=”’FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth”’

palins=[]

def palindrome():

for i in range(len(txt)-1):

#print “iteration:”+str(i)

j=len(txt)-1

while(j>=i):

#check plaindrome

temp=txt[i:j]

last=len(temp)-1

iters=int(len(temp)/2)

flag=True

for n in range(iters):

if temp[n]!=temp[last-n]:

flag=False

break

if flag==True:

palins.append(temp)

j-=1

def getmax(li):

longest=”

for i in li:

if len(i) > len(longest):

longest=i

return (longest,len(longest))

palindrome()

print “longest palindrome: %s, size:%d” % getmax(palins)

O(n^2) solution in Scheme

> I’m still looking for the “perfect” solution that I can use for an exercise

solution based on coin change algorithm gives an answer almost instantly.

Here’s the O(n^2) solution in Matlab:

function longest_palindrom_quad()

%O(n^2) solution

txt = [‘Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta’ …

‘inentanewnationconceivedinzLibertyanddedicatedtotheproposit’ …

‘ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa’ …

‘rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic’ …

‘atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh’ …

‘avecometodedicpateaportionofthatfieldasafinalrestingplacefo’ …

‘rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog’ …

‘etherfangandproperthatweshoulddothisButinalargersensewecann’ …

‘otdedicatewecannotconsecratewecannothallowthisgroundThebrav’ …

‘elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove’ …

‘ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl’ …

‘ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI’ …

’tisforusthelivingrathertobededicatedheretotheulnfinishedwor’ …

‘kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather’ …

‘forustobeherededicatedtothegreattdafskremainingbeforeusthat’ …

‘fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh’ …

‘ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres’ …

‘olvethatthesedeadshallnothavediedinvainthatthisnationunsder’ …

‘Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb’ …

‘ythepeopleforthepeopleshallnotperishfromtheearth’];

n = length(txt);

palindrom_length = -inf;

palindrom = [];

for idx = 1:n

[odd_found, odd_span] = extend_odd(idx);

if odd_found

odd_len = 2*odd_span+1;

if odd_len > palindrom_length

palindrom = [idx – odd_span, idx + odd_span];

palindrom_length = odd_len;

end

end

[even_found, even_span] = extend_even(idx);

if even_found

even_len = 2*even_span;

if even_len > palindrom_length

palindrom = [idx – (even_span-1), idx + even_span];

palindrom_length = odd_len;

end

end

end

disp([‘palindrom is ‘ txt(palindrom(1):palindrom(2)) ]);

disp([‘length is ‘ num2str(palindrom_length)]);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [odd_found, odd_span] = extend_odd(odd_i)

flag = false;

oi = 1;

while(odd_i – oi >= 1 && odd_i + oi <= n)

if txt(odd_i – oi) == txt(odd_i + oi)

flag = true;

else

break;

end

oi = oi + 1;

end

if flag

odd_found = true;

odd_span = oi-1;

else

odd_found = false;

odd_span = nan;

end

end

function [even_found, even_span] = extend_even(even_i)

flag = false;

oi = 1;

while(even_i – (oi – 1) <= n && even_i + oi <= n)

if txt(even_i + oi) == txt(even_i – (oi – 1))

flag = true;

else

break;

end

oi = oi + 1;

end

if flag

even_found = true;

even_span = oi-1;

else

even_found = false;

even_span = nan;

end

end

end

Here is a solution in golang. It runs pretty fast, just 0.1 s

to compile, link, and run, in a Linux inside VirtualBox.

You can run it on golang.org.

(It took substantially longer time to write. This is my first program in golang.)

http://pastebin.com/embed_iframe.php?i=SiiKi8Yp

[…] Find the Longest Palindrome in a string: […]

Here is a more challenging test-case for your algorithms:

In the collected works of Shakespeare, there are 3 palindromes of 15 characters each — no Shakespearean palindrome is longer. Two are the phrase “Madam, madam, madam.” which is fairly easy to find. What’s the third?

[…] sure how I came across the Programming Praxis blog, but one of their recent posts caught my eye: find the longest palindrome in a string. Given a string, what is the longest palindrome contained in that string? I thought about it […]

Here is a solution in Factor:

http://re-factor.blogspot.com/2010/10/longest-palindrome.html

Mine in F#

Mine in F#

my C implementation

http://codepad.org/Rcp5KmqC</a.

my C implementation

http://codepad.org/Rcp5KmqC

def longest_palindrome(S):

longest, n = ”, len(S)

if n = 0 and j < n:

if S[i] == S[j]:

L.append(S[i])

else:

break

i -= 1

j += 1

if L:

return ''.join(L[::-1] + M + L)

return ''

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace CountPalindrome

{

class Program

{

static void Main(string[] args)

{

Console.WriteLine(“please input a string: “);

string test = Convert.ToString(Console.ReadLine());

Console.WriteLine(“the longest palindrome is ” + LongestPalindrome(test));

Console.ReadLine();

}

protected static int LongestPalindrome(string str)

{

int i = 0;

int j = 1;

int oldJ = 1;

int intMax = 1;

int intCount = 0;

if (str.Length == 0) return 0;

if (str.Length == 1) return 1;

int[] intDistance = new int[2] {0,1};

for( int k = 0; k < intDistance.Length; k++ ){

j = 1 + intDistance[k];

oldJ = j;

intCount = 0;

i = 0;

while (j = 0 && j b) return a; return b;

}

}

}

Reblogged this on rajispassionate.

Here’s the solution in O(n^2) : “ranynar”

https://github.com/huei90/leetcode-js/longest-palindrome-substring.js

“`

(function () {

var expandAroundCenter = function expandAroundCenter(s, c1, c2) {

var l = c1,

r = c2,

n = s.length;

while (l >= 0 && r <= n – 1 && s[l] == s[r]) {

l–;

r++;

}

return s.substr(l + 1, r – l – 1);

};

var longestPalindromeSimple = function longestPalindromeSimple(s) {

var n = s.length;

if (n == 0) {

return '';

}

var longest = s[0]; // a single char itself is a palindrome

for (var i = 0; i longest.length) {

longest = p1;

}

var p2 = expandAroundCenter(s, i, i + 1);

if (p2.length > longest.length) {

longest = p2;

}

}

return longest;

};

longestPalindromeSimple(‘bananad’); // => anana

// such as Tragedy @@

})();

“`

public class LongestPalindromicSubstring {

public static void main(String[] args) {

// TODO Auto-generated method stub

System.out.println(longestPalindrome(“FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth”));

}

public static String longestPalindrome(String s) {

String maxStr = “”;

for(int i = s.length();i >= 0;i –){

maxStr = isPalindrom(s, i);

if(maxStr.length() !=0)

break;

}

return maxStr;

}

public static String isPalindrom(String s,int len){

int i = 0;

StringBuffer str = new StringBuffer(s);

String str1;

String str2;

String str3 = “”;

while(i + len <= s.length()){

str1 = str.substring(i,i + len).toString();

StringBuffer str4 = new StringBuffer(str1);

str2 = str4.reverse().toString();

if(str1.equals(str2) && str3.length() < str1.length()){

str3 = str1;

break;

}

else{

i ++;

}

}

return str3;

}

}