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

Posted by programmingpraxis
Filed in Exercises
29 Comments »

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

  1. Grégory LEOCADIE said
    October 15, 2010 at 11:19 AM

    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. Programming Praxis – Find The Longest Palindrome In A String « Bonsai Code said
    October 15, 2010 at 12:17 PM

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

  3. Remco Niemeijer said
    October 15, 2010 at 12:18 PM

    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]
  4. programmingpraxis said
    October 15, 2010 at 1:27 PM

    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
    October 15, 2010 at 2:30 PM

    My solution in Python:

    #!/usr/bin/env python
import sys

def main(args):
	try:
		with open(args[1]) as f:
			stream = f.read()
	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
    October 15, 2010 at 8:33 PM

    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
  7. Brandon Tilley said
    October 15, 2010 at 9:47 PM


    #!/usr/bin/env ruby
    ## Find The Longest Palindrome In A String
    ## October 15, 2010
    ##
    ## https://programmingpraxis.com/2010/10/15/find-the-longest-palindrome-in-a-string/
    ##
    ## 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.
    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
    ythepeopleforthepeopleshallnotperishfromtheearth

    view raw

    longest_palindrome.rb

    hosted with ❤ by GitHub 

    #!/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
ythepeopleforthepeopleshallnotperishfromtheearth
  8. Graham said
    October 15, 2010 at 10:01 PM

    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. Brandon Tilley said
    October 15, 2010 at 11:02 PM

    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
ythepeopleforthepeopleshallnotperishfromtheearth
  10. Brandon Tilley said
    October 15, 2010 at 11:03 PM

    Hurray for leaving debugging code in the post >.<

  11. pradyumna chatterjee said
    October 16, 2010 at 6:33 AM

    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)

  12. Dmitry said
    October 16, 2010 at 4:40 PM

    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.

  13. lalit mohan said
    October 17, 2010 at 7:52 AM

    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

  14. Lars Björnfot said
    October 20, 2010 at 11:38 PM

    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
}
  16. Find the Longest Palindrome in a String » JOEZACK.COM said
    October 21, 2010 at 3:51 AM

    […] Find the Longest Palindrome in a string: […]

  17. F. Carr said
    October 23, 2010 at 9:53 PM

    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?

  18. Palindromes in Python « ∑idiot's Blog said
    October 24, 2010 at 3:49 AM

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

  20. KNguyen said
    October 28, 2010 at 9:38 PM

    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
  21. KNguyen said
    October 28, 2010 at 9:40 PM

    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
  24. Lautaro Pecile said
    March 17, 2011 at 5:26 PM 
    
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
  25. zhizhong said
    May 13, 2011 at 10:08 PM

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

  26. Robert Grano said
    June 29, 2013 at 10:46 PM

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

    }
    }

  28. Huei Tan said
    October 24, 2014 at 6:42 AM

    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 @@
    })();
    “`

  29. Yi Gan said
    May 16, 2015 at 9:22 PM

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

Leave a comment