Ruby - Finding the longest palindromic substring in a string

1
votes

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
4
rubystringsubstringreversepalindrome
You would need to implement something like the Manacher's algorithm to solve this problem. en.wikipedia.org/wiki/Longest_palindromic_substring - Benji
You don't need to use a fancy linear time algorithm. It would be easier (and perhaps sufficient) to use a naive O(n^2) algorithm. - Max

4 Answers

3
votes

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
2
votes
def longest_palindrome(string)
  longest = ''
  i = 0
  while i < string.length
    j = 1
    while (i + j) <= string.length
      x = string.slice(i, j)
      if (x.length > longest.length) && (x == x.reverse)
        longest = x
      end
      j += 1
    end
    i += 1
  end
  longest
end

The slice method is handy to have for solving this problem. Test each substring with the classic double while loop approach with (i, j) representing a starting index and length of the substring respectively. string.slice(start_index, substring_length)

The String#slice method works like this:

"bdehannahc".slice(3, 8) == "hannah" # which is a palindrome and would be 
                                     # found by the method introduced above
1
votes

This checks if the entire string str is a palindrome. If it is, we're finished; if not, check all substrings of length str.size-1. If one is a palindrome, we're finished; if not, check substrings of length str.size-1, and so on. 

def longest_palindrome(str)
  arr = str.downcase.chars
  str.length.downto(1) do |n|
    ana = arr.each_cons(n).find { |b| b == b.reverse }
    return ana.join if ana
  end
end

longest_palindrome "abcdxyzyxabcdaaa"
  #=> "xyzyx"
longest_palindrome "abcdefghba"
  #=> "a"

The key method here is Enumerable#each_cons.

-1
votes

Here is another solution, using less features of Ruby and iteration instead of recursion:

def longest_palindrome(string)
  # to find the longest palindrome, start with whole thing
  substr_start = 0
  substr_length = string.length
  while substr_length > 0 # 1 is a trivial palindrome and the end case
#    puts 'substr_length is:' + substr_length.to_s
    while substr_start <= string.length - substr_length
#      puts 'start is: ' + substr_start.to_s
      if palindrome?(string.slice(substr_start,substr_length))
        puts 'found palindrome: ' + string.slice(substr_start,substr_length)
        return string.slice(substr_start,substr_length)
      end
      substr_start += 1
    end
    substr_start = 0 # inner loop ctr reset
    substr_length -= 1
  end
  puts 'null string tested?'
  return ''
end