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):
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]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.
#!/usr/bin/python txt = open('gettysburg.txt').read() 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#!/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 = DATA.read.gsub "\n", "" string.downcase! puts longest_palindrome_in string __END__ Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta inentanewnationconceivedinzLibertyanddedicatedtotheproposit ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh avecometodedicpateaportionofthatfieldasafinalrestingplacefo rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog etherfangandproperthatweshoulddothisButinalargersensewecann otdedicatewecannotconsecratewecannothallowthisgroundThebrav elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI tisforusthelivingrathertobededicatedheretotheulnfinishedwor kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather forustobeherededicatedtothegreattdafskremainingbeforeusthat fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres olvethatthesedeadshallnothavediedinvainthatthisnationunsder Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb ythepeopleforthepeopleshallnotperishfromtheearthI 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()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 = DATA.read.gsub "\n", "" string.downcase! puts PalindromeFinder::find string __END__ Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta inentanewnationconceivedinzLibertyanddedicatedtotheproposit ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh avecometodedicpateaportionofthatfieldasafinalrestingplacefo rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog etherfangandproperthatweshoulddothisButinalargersensewecann otdedicatewecannotconsecratewecannothallowthisgroundThebrav elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI tisforusthelivingrathertobededicatedheretotheulnfinishedwor kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather forustobeherededicatedtothegreattdafskremainingbeforeusthat fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres olvethatthesedeadshallnothavediedinvainthatthisnationunsder Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb ythepeopleforthepeopleshallnotperishfromtheearthHurray 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
; 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 (define (longest-int from current-answer) (if (>= from (vector-length v)) current-answer (let ((candidate (range-for from))) (if (> (range-length candidate) (range-length current-answer)) (longest-int (+ 1 from) candidate) (longest-int (+ 1 from) current-answer))))) (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.
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.)
package main func main() { input := "Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta"+ "inentanewnationconceivedinzLibertyanddedicatedtotheproposit"+ "ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa"+ "rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic"+ "atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh"+ "avecometodedicpateaportionofthatfieldasafinalrestingplacefo"+ "rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog"+ "etherfangandproperthatweshoulddothisButinalargersensewecann"+ "otdedicatewecannotconsecratewecannothallowthisgroundThebrav"+ "elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove"+ "ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl"+ "ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI"+ "tisforusthelivingrathertobededicatedheretotheulnfinishedwor"+ "kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather"+ "forustobeherededicatedtothegreattdafskremainingbeforeusthat"+ "fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh"+ "ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres"+ "olvethatthesedeadshallnothavediedinvainthatthisnationunsder"+ "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 }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#
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 tttMine 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 tttmy C implementation
http://codepad.org/Rcp5KmqC</a.
my C implementation
http://codepad.org/Rcp5KmqC
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 edef 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;
}
}