## 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(n3) 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(n2) 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.

Pages: 1 2

### 29 Responses to “Find The Longest Palindrome In A String”

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

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

3. Remco Niemeijer said

```import qualified Data.ByteString.Char8 as B
import qualified Data.List.Key as K

longestPalindrome :: B.ByteString -> B.ByteString
longestPalindrome s = K.maximum B.length
[p | p <- B.inits =<< B.tails s, p == B.reverse p]
```
4. programmingpraxis said

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

5. Bogdan Popa said

My solution in Python:

```#!/usr/bin/env python
import sys

def main(args):
try:
with open(args[1]) as f:
except IndexError:
print "usage: pal.py file"
return 0
except IOError:
print "error: could not open file '%s'." % args[1]
return 1

longest = ""

for i, _ in enumerate(stream):
for j, _ in enumerate(stream[i:]):
if stream[i:j] == stream[j-1:i-1:-1] and j - i > len(longest):
longest = stream[i:j]

print longest

return 0

if __name__ == "__main__":
sys.exit(main(sys.argv))
```
6. kbob said

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.

```#!/usr/bin/python

longest = ''

def nominate(s):
global longest
if len(s) > len(longest):
longest = s

def explore(i, j):
"""[i..j] is closed interval"""
while 0 <= i and j < len(txt) and txt[i] == txt[j]:
i -= 1
j += 1
nominate(txt[i+1:j])

# Odd-length substrings
for i in range(1, len(txt) - 1):
explore(i, i)

# Even-length substrings
for i in range(1, len(txt)):
explore(i - 1, i)

print longest
```
7. ```#!/usr/bin/env ruby

def longest_palindrome_in(string)
palindrome = ""
0.upto string.length do |outer|
string.length.downto outer+1 do |inner|
forward = string.slice(outer..inner)
if forward.length > palindrome.length && forward.eql?(forward.reverse)
palindrome = forward
end
end
end
palindrome
end

string.downcase!
puts longest_palindrome_in string

__END__

Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta
inentanewnationconceivedinzLibertyanddedicatedtotheproposit
ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa
rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic
atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh
avecometodedicpateaportionofthatfieldasafinalrestingplacefo
rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog
etherfangandproperthatweshoulddothisButinalargersensewecann
otdedicatewecannotconsecratewecannothallowthisgroundThebrav
ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI
tisforusthelivingrathertobededicatedheretotheulnfinishedwor
forustobeherededicatedtothegreattdafskremainingbeforeusthat
ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres
Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb
ythepeopleforthepeopleshallnotperishfromtheearth
```
8. Graham said

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.

```#!/usr/bin/env python
# Find the longest palindrome in a given text

def is_pal(s):
return s == s[::-1]

def flp(s):
longest, len_longest  = 'g', 1
for i in xrange(len(s)):
for j in xrange(2,len(s[i:])):
sub_s = s[i:i+j+1]
if is_pal(sub_s) and len(sub_s) > len_longest:
longest, len_longest = sub_s, j+1
return (longest, len_longest)

def main():
f = open('four_score.txt')
lines =  ''.join(l for l in f.read().split())
f.close()
pal, length = flp(lines)
print "Length of longest palindrome:\t%s" % length
print "Longest palindrome:\t%s" % pal
return

if __name__ == '__main__':
main()
```
9. And here’s my go at the O(n^2) solution described in the post, in Ruby:

```#!/usr/bin/env ruby

class PalindromeFinder
def self.find(string)
longest = ""

(0...string.length).each do |count|
palindrome = find_longest_palindrome_at_char string, count
longest = palindrome if !palindrome.nil? && palindrome.length > longest.length
end

longest
end

# Return the longest palindrome in the given string using the character
# at the position given as the midpoint of the search string.
def self.find_longest_palindrome_at_char(string, position)
max_string = string.slice 0..position
found = nil
(1..max_string.length/2).each do |count|
potential = mid max_string, count
return found unless palindrome? potential
found = potential
end
found
end

# Return the middle of the given string,
# counting count characters left and right.
def self.mid(string, count)
length    = string.length
mid       = length / 2
start_pos = mid - count
end_pos   = string.length.even? ? mid + (count - 1) : mid + count

puts "ERROR #{string} #{count} #{mid} #{start_pos} #{end_pos}" if start_pos < 0 || end_pos >= length
string.slice start_pos..end_pos
end

# Return true if the given string is a palindrome.
def self.palindrome?(string)
true if !string.nil? && string.eql?(string.reverse)
end
end

string.downcase!
puts PalindromeFinder::find string

__END__

Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta
inentanewnationconceivedinzLibertyanddedicatedtotheproposit
ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa
rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic
atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh
avecometodedicpateaportionofthatfieldasafinalrestingplacefo
rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog
etherfangandproperthatweshoulddothisButinalargersensewecann
otdedicatewecannotconsecratewecannothallowthisgroundThebrav
ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI
tisforusthelivingrathertobededicatedheretotheulnfinishedwor
forustobeherededicatedtothegreattdafskremainingbeforeusthat
ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres
Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb
ythepeopleforthepeopleshallnotperishfromtheearth
```
10. Hurray for leaving debugging code in the post >.<

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)

12. Dmitry said

O(n^2) solution in Scheme

```
; range

(define make-range cons)
(define range-from car)
(define range-to cdr)

(define (range-length r)
(- (range-to r)
(range-from r)))

; vector[from, to) -> string

(define (subvector->list v range)
(define (s->l from to)
(if (>= from to)
(list)
(cons (vector-ref v from)
(s->l (+ 1 from) to))))
(s->l (range-from range)
(range-to range)))

; palindrome stuff

(define (longest-palindrome-range v)

; v[first] == vector[second]
(define (pal-pair? first second)
(if (or (< first 0) (>= second (vector-length v)))
#f
(eq? (vector-ref v first)
(vector-ref v second))))

; longest palindrome range for position
(define (range-for pos)
(define (range-int from to)
(if (pal-pair? from to)
(range-int (- from 1) (+ to 1))
(make-range (+ from 1) to)))

(let ((odd-p (range-int pos pos))
(even-p (range-int pos (+ pos 1))))
(if (> (range-length odd-p)
(range-length even-p))
odd-p
even-p)))

; search
(if (>= from (vector-length v))
(let ((candidate (range-for from)))
(if (> (range-length candidate)
(longest-int (+ 1 from) candidate)
(longest-int 0 (make-range 0 0)))

(define (longest-palindrome str)
(let* ((v (list->vector (string->list str)))
(range (longest-palindrome-range v)))
(list->string (subvector->list v range))))

; usage

(longest-palindrome "problem string")

```

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

13. lalit mohan said

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

%O(n^2) solution

txt = [‘Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta’ …
‘inentanewnationconceivedinzLibertyanddedicatedtotheproposit’ …
‘ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa’ …
‘rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic’ …
‘atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh’ …
‘avecometodedicpateaportionofthatfieldasafinalrestingplacefo’ …
‘rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog’ …
‘etherfangandproperthatweshoulddothisButinalargersensewecann’ …
‘otdedicatewecannotconsecratewecannothallowthisgroundThebrav’ …
‘ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI’ …
’tisforusthelivingrathertobededicatedheretotheulnfinishedwor’ …
‘forustobeherededicatedtothegreattdafskremainingbeforeusthat’ …
‘ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres’ …
‘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

14. Lars Björnfot said

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

```package main

func main() {
input :=
"Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta"+
"inentanewnationconceivedinzLibertyanddedicatedtotheproposit"+
"ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa"+
"rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic"+
"atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh"+
"avecometodedicpateaportionofthatfieldasafinalrestingplacefo"+
"rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog"+
"etherfangandproperthatweshoulddothisButinalargersensewecann"+
"otdedicatewecannotconsecratewecannothallowthisgroundThebrav"+
"ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI"+
"tisforusthelivingrathertobededicatedheretotheulnfinishedwor"+
"forustobeherededicatedtothegreattdafskremainingbeforeusthat"+
"ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres"+
"Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb"+
"ythepeopleforthepeopleshallnotperishfromtheearth"
var palin string
for i := 0; i < len(input) - 1; i++ {
palin = larger(palin, input, i, i)
palin = larger(palin, input, i, i+1)
}
println("Max palin: ", palin)
}
func larger(palin string, s string, i int, j int) string {
var p = getPalin(s, i, j)
if len(p) > len(palin) {
return p
}
return palin
}
func getPalin(s string, i int, j int) string {
for i >= 0 && j < len(s) && s[i] == s[j] {
i--
j++
}
i++            // adjust start index, end index is fine
return s[i:j]  // return palindrome
}
```
15. […] Find the Longest Palindrome in a string: […]

16. F. Carr said

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?

17. […] 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 […]

18. KNguyen said

Mine in F#

```
let isPalindrome (s:string) =
List.ofArray (s.ToCharArray()) = List.rev (List.ofArray (s.ToCharArray()))

let rec longest_palin_from_start (s:string) =
if (isPalindrome s) then s
else
let length = s.Length
longest_palin_from_start (s.Substring(0, length-1))

let rec longest_palin_in_string (s:string) =
if (s.Length = 1) then s
else
let tt = longest_palin_from_start s
let ttt = longest_palin_in_string (s.Substring(1))
if (tt.Length > ttt.Length) then tt else ttt
```
19. KNguyen said

Mine in F#

```let isPalindrome (s:string) =
List.ofArray (s.ToCharArray()) = List.rev (List.ofArray (s.ToCharArray()))

let rec longest_palin_from_start (s:string) =
if (isPalindrome s) then s
else
let length = s.Length
longest_palin_from_start (s.Substring(0, length-1))

let rec longest_palin_in_string (s:string) =
if (s.Length = 1) then s
else
let tt = longest_palin_from_start s
let ttt = longest_palin_in_string (s.Substring(1))
if (tt.Length > ttt.Length) then tt else ttt
```
20. Lautaro Pecile said
```
def substrings(s):
"""
Yields substrings from string s in descending order
"""
l = len(s)
for end in xrange(l, 0, -1):
for start in xrange(l-end+1):
yield s[start:start + end]

def palindrome(s):
return s == s[::-1]

def longest_palindrome(s):
for e in substrings(s):
if palindrome(e):
return e
```
21. zhizhong said

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 ''

22. Robert Grano said

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CountPalindrome
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine(“the longest palindrome is ” + LongestPalindrome(test));
}
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;
}

}
}

23. Huei Tan said

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

// such as Tragedy @@
})();
“`

24. Yi Gan said

public class LongestPalindromicSubstring {

public static void main(String[] args) {
// TODO Auto-generated method stub
}

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