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.

Advertisements

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

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 Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out / Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out / Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out / Change )

Google+ photo

You are commenting using your Google+ account. ( Log Out / Change )

Cancel

Connecting to %s

%d bloggers like this: