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.

About these ads

Pages: 1 2

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

  1. Grégory LEOCADIE said

    Could someone delete my previous comment please ?

    I tried the naive way. I don’t know much about palindrome.
    oops my pastebin does not show up. my solution

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

  3. Remco Niemeijer said

    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

    Remco: I also used the O(n^3) algorithm when I solved the challenge; I wrote the code as fast as I can type, it worked the first time, and once I had the answer I moved on to the second level. But after I finished the challenge I went looking for a better way, and Jeuring’s solution was so pretty I had to include it in an exercise.

    By the way, the second level was easy, involving fibonacci numbers, prime checking and integer factorization; I could have stolen code from several of our earlier exercises to solve it quickly, but instead I looked up the prime fibonacci numbers on OEIS and used Dario Alpern’s applet for the factorization. The third level involved generating all possible subsets and testing them for a particular condition, and the brute-force solution took over a minute to run. I’ve since got a much better solution for the third level, but I’m still looking for the “perfect” solution that I can use for an exercise.

    Phil

  5. Bogdan Popa said

    My solution in Python:

    #!/usr/bin/env python
    import sys
    
    def main(args):
    	try:
    		with open(args[1]) as f:
    			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

    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. #!/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

    I also did the slow and steady method. O(n^3) isn’t bad for 1169 characters, but it won’t be great for larger data. Small speed up: in my flp() function, starting case is a single character, so we begin by only searching for palindromes of length 2 or greater.

    #!/usr/bin/env python
    # Find the longest palindrome in a given text
    
    def is_pal(s):
        return s == s[::-1]
    
    def flp(s):
        longest, len_longest  = 'g', 1
        for i in xrange(len(s)):
            for j in xrange(2,len(s[i:])):
                sub_s = s[i:i+j+1]
                if is_pal(sub_s) and len(sub_s) > len_longest:
                    longest, len_longest = sub_s, j+1
        return (longest, len_longest)
    
    def main():
        f = open('four_score.txt')
        lines =  ''.join(l for l in f.read().split())
        f.close()
        pal, length = flp(lines)
        print "Length of longest palindrome:\t%s" % length
        print "Longest palindrome:\t%s" % pal
        return
    
    if __name__ == '__main__':
        main()
    
  9. And here’s my go at the O(n^2) solution described in the post, in Ruby:

    #!/usr/bin/env ruby
    
    class PalindromeFinder
      def self.find(string)
        longest = ""
    
        (0...string.length).each do |count|
          palindrome = find_longest_palindrome_at_char string, count
          longest = palindrome if !palindrome.nil? && palindrome.length > longest.length
        end
    
        longest
      end
    
      # Return the longest palindrome in the given string using the character
      # at the position given as the midpoint of the search string.
      def self.find_longest_palindrome_at_char(string, position)
        max_string = string.slice 0..position
        found = nil
        (1..max_string.length/2).each do |count|
          potential = mid max_string, count
          return found unless palindrome? potential
          found = potential
        end
        found
      end
    
      # Return the middle of the given string,
      # counting count characters left and right.
      def self.mid(string, count)
        length    = string.length
        mid       = length / 2
        start_pos = mid - count
        end_pos   = string.length.even? ? mid + (count - 1) : mid + count
    
        puts "ERROR #{string} #{count} #{mid} #{start_pos} #{end_pos}" if start_pos < 0 || end_pos >= length
        string.slice start_pos..end_pos
      end
    
      # Return true if the given string is a palindrome.
      def self.palindrome?(string)
        true if !string.nil? && string.eql?(string.reverse)
      end
    end
    
    string = 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. Hurray for leaving debugging code in the post >.<

  11. pradyumna chatterjee said

    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

    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

    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

    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
    }
    
  15. [...] Find the Longest Palindrome in a string: [...]

  16. F. Carr said

    Here is a more challenging test-case for your algorithms:

    In the collected works of Shakespeare, there are 3 palindromes of 15 characters each — no Shakespearean palindrome is longer. Two are the phrase “Madam, madam, madam.” which is fairly easy to find. What’s the third?

  17. [...] sure how I came across the Programming Praxis blog, but one of their recent posts caught my eye: find the longest palindrome in a string. Given a string, what is the longest palindrome contained in that string? I thought about it [...]

  18. KNguyen said

    Mine in F#

    
    let isPalindrome (s:string) = 
        List.ofArray (s.ToCharArray()) = List.rev (List.ofArray (s.ToCharArray()))
    
    let rec longest_palin_from_start (s:string) =
        if (isPalindrome s) then s 
        else 
            let length = s.Length
            longest_palin_from_start (s.Substring(0, length-1))
    
    let rec longest_palin_in_string (s:string) = 
        if (s.Length = 1) then s
        else
            let tt = longest_palin_from_start s
            let ttt = longest_palin_in_string (s.Substring(1))
            if (tt.Length > ttt.Length) then tt else ttt
    
  19. KNguyen said

    Mine in F#

    let isPalindrome (s:string) = 
        List.ofArray (s.ToCharArray()) = List.rev (List.ofArray (s.ToCharArray()))
    
    let rec longest_palin_from_start (s:string) =
        if (isPalindrome s) then s 
        else 
            let length = s.Length
            longest_palin_from_start (s.Substring(0, length-1))
    
    let rec longest_palin_in_string (s:string) = 
        if (s.Length = 1) then s
        else
            let tt = longest_palin_from_start s
            let ttt = longest_palin_in_string (s.Substring(1))
            if (tt.Length > ttt.Length) then tt else ttt
    
  20. Lautaro Pecile said
    
    def substrings(s):
        """
        Yields substrings from string s in descending order
        """
        l = len(s)
        for end in xrange(l, 0, -1):
            for start in xrange(l-end+1):
                yield s[start:start + end]
    
    def palindrome(s):
        return s == s[::-1]
    
    def longest_palindrome(s):
        for e in substrings(s):
            if palindrome(e):
                return e
    
  21. zhizhong said

    def longest_palindrome(S):
    longest, n = ”, len(S)
    if n = 0 and j < n:
    if S[i] == S[j]:
    L.append(S[i])
    else:
    break
    i -= 1
    j += 1

    if L:
    return ''.join(L[::-1] + M + L)
    return ''

  22. Robert Grano said

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    namespace CountPalindrome
    {
    class Program
    {
    static void Main(string[] args)
    {
    Console.WriteLine(“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;
    }

    }
    }

Leave a Reply

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

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 )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 609 other followers

%d bloggers like this: