## 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
ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI
tisforusthelivingrathertobededicatedheretotheulnfinishedwor
forustobeherededicatedtothegreattdafskremainingbeforeusthat
ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres
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.

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