Algorithm #3029823450

Aug 8, 2016 · 3 min read

“Given a string, find the longest palindrome that can be constructed by removing or shuffling characters from the string. Return only one palindrome if there are multiple palindrome strings of longest length.”

`# remember: palindromes must have the same letter at [0] and [-1], [1] and [-2], etc.  # scan the string for duplicate letters  # return a single letter if no duplicate letters exist  # when a pair of letters is found, add them to beginning and end of new string, and remove them both from the original string  # if, when no pairs are left, there are still characters remaining in the string, add one of them to the string at index [string.length/2]`
`def longest_pal(str)  longest = []  loop do     alpha = str.scan(/([a-z])/)[0][0]    all_of_alpha = str.scan(/#{alpha}/)    letter = all_of_alpha[0]    if all_of_alpha.length >= 2      remaining = all_of_alpha.length - 2      longest.insert(0, letter)      longest.insert(-1, letter)      str.delete!(letter)            remaining.times do         str << letter      end    end    break unless str.each_char.find { |c| str.count(c) > 1 }   end  letter = str.scan(/([a-z])/)[0][0]  longest.insert(longest.length/2, letter) unless str.empty?  longest.joinend`
`def longest_pal(str)  beg = ""  mid = ""  count = {}  i = 0  while i < str.length    count[str[i]] ||= 0     count[str[i]] += 1    i += 1  end  count.keys.each do |letter|    if count[letter].odd?      mid = letter       count[letter] -= 1    else       i = 0      while i < count[letter]/2        beg << letter        i += 1      end    end  end  last = beg.reverse  "#{beg}#{mid}#{last}"end`

Written by

Matt Hinea

Web Developer

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just \$5/month. Upgrade