public
Last active

O(n^3) Solution for Programming Praxis 2010-10-15: Find The Longest Palindrome In A String

  • Download Gist
longest_palindrome.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
#!/usr/bin/env ruby
 
## Find The Longest Palindrome In A String
## October 15, 2010
##
## http://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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.