## 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.

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;

}

}