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.
longest_palindrome.rb
hosted with ❤ by GitHub
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;
}
}