Darkmouse Darkmouse - 1 month ago 13
Ruby Question

Ruby - Finding the longest palindromic substring in a string

I understand how to find if one string is a palindrome

string1 == string1.reverse


It's a little more difficult though with multiple palindromes in a string

"abcdxyzyxabcdaaa"


In the above string, there are 4 palindromes of length greater than 1

"xyzyx", "yzy", "aaa" and "aa"


In this case, the longest palindrome is "xyxyx", which is 5 characters long.

How would I go about solving this problem though.

I know of the array#combination method, but that won't work in this case.

I was thinking of implementing something like this

def longest_palindrome(string)
palindromes = []
for i in 2..string.length-1
string.chars.each_cons(i).each {|x|palindromes.push(x) if x == x.reverse}
end
palindromes.map(&:join).max_by(&:length)
end

Answer

If your just looking for the largest palindrome substring, Here is a quick and dirty solution.

def longest_palindrome(string, size)
  string.size.times do |start| # loop over the size of the string
    break if start + size > string.size # bounds check

    reverse = string[start, size].reverse

    if string.include? reverse #look for palindrome
      return reverse #return the largest palindrome
    end
  end
  longest_palindrome(string, size - 1) # Palindrome not found, lets look for the next smallest size 
end