## Find The Longest Palindrome In A String

### October 15, 2010

There are several ways to attack this problem. The easiest is to form all possible substrings of the original, test each substring to see if it is a palindrome, and keep the longest. That’s an *O*(*n*^{3}) algorithm, since the substrings are generated in two nested loops that each iterate over the length of the string, and the test for palindromeness (palindromity, perhaps?) requires another pass over the substring. It works fine for strings as short as the challenge string, but it doesn’t scale to larger strings.

A better approach that works in *O*(*n*^{2}) time looks for odd-length and even-length palindromes separately. For odd-length palindromes, each character forms a palindrome of length one, and it can be extended while the characters on each side are the same, as long as the edge of the string isn’t reached. Searching for even-length palindromes is the same, except that the starting point is each position between characters, which is a zero-length palindrome. The algorithm loops through the string, finding the maximum-length palindrome starting at each character and position-between-characters, keeping the longest.

It is possible to solve this problem in linear time using a suffix trie. But the code to do that is quite tricky, and if done improperly the program to build the suffix trie takes quadratic time, defeating the linear time complexity of the solution. The suffix trie also takes much space, which is prohibitive for large inputs.

A bit of searching turns up a blog entry by Johan Jeuring, who is well-known in the functional programming community. His solution, given in Haskell, is beautiful. Here is our version translated directly to Scheme; we even kept Jeuring’s British spelling of center:

`(define (longest-palindrome input)`

(let* ((lps (reverse (longest-palindromes input)))

(max-length-pos

(maximum-by

(lambda (a b) (< (car a) (car b)))

(zip lps (range (length lps))))))

(show-palindrome input (car max-length-pos) (cadr max-length-pos))))

`(define (show-palindrome s len pos)`

(let ((startpos (- (quotient pos 2) (quotient len 2)))

(endpos (if (odd? len)

(+ (quotient pos 2) (quotient len 2))

(+ (quotient pos 2) (quotient len 2) -1))))

(substring s startpos (+ endpos 1))))

`(define (longest-palindromes a)`

(let ((afirst 0) (alast (string-length a)))

(extend-tail a afirst 0 '())))

`(define (extend-tail a n current-tail centres)`

(let ((afirst 0) (alast (string-length a)))

(cond ((>= n alast)

(final-centres current-tail centres (cons current-tail centres)))

((= (- n current-tail) afirst)

(extend-centres a n (cons current-tail centres) centres current-tail))

((char=? (string-ref a n) (string-ref a (- n current-tail 1)))

(extend-tail a (+ n 1) (+ current-tail 2) centres))

(else

(extend-centres a n (cons current-tail centres) centres current-tail)))))

`(define (extend-centres a n centres tcentres centre-distance)`

(cond ((= centre-distance 0)

(extend-tail a (+ n 1) 1 centres))

((= (- centre-distance 1) (car tcentres))

(extend-tail a n (car tcentres) centres))

(else (extend-centres a n

(cons (min (car tcentres) (- centre-distance 1)) centres)

(cdr tcentres) (- centre-distance 1)))))

`(define (final-centres n+1 tcentres centres)`

(if (= n+1 0)

centres

(final-centres (- n+1 1) (cdr tcentres)

(cons (min (car tcentres) (- n+1 1)) centres)))))

We won’t try to explain the code shown above; Jeuring does it perfectly well.

We used `range`

, `zip`

, and the newly-added `maximum-by`

from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/HuGrtndJ.

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;

}

}