longest_palindrome.rb

longest_palindrome.rb

# Ruby problem exercise from: http://www.rubeque.com/problems/a-man-comma--a-plan-comma--a-canal--panama-excl-

# We've covered the above problem at Brainstation Toronto: Backend Programming - First Cohort. (http://brainstation.it)

# The following solution is O(N^2)
# I've deliberately kept is as such (O(N^2)) so as to make sure 
# It's easier to explain to the students. 

def palindrome?(str)
  str == str.reverse
end

def longest_palindrome(string)
  length = string.length
  palindromes = []
  
  string.split("").each_with_index do |char, index|

    if index >= 1 && index < length-2
      right_room = string[index..-1].length
      left_room = string[0..index].length
      allowable_room = [right_room, left_room].min - 1
      
      (1..allowable_room).each do |possible_allowable_room|
        odd_test_str = string[(index-possible_allowable_room)..(index+possible_allowable_room)]
        even_test_str = string[(index-possible_allowable_room)..(index+1+possible_allowable_room)]
        palindromes << odd_test_str if palindrome?(odd_test_str)
        palindromes << even_test_str if palindrome?(even_test_str)
      end

    end

  end
  puts palindromes.max_by { |elem| elem.length }
end

longest_palindrome("xyxy")
longest_palindrome("rabbac")
longest_palindrome("nnnbaxyxab")
longest_palindrome("afbbbfjdjklgdfdhfdkjfffhhfffjkdfhdhkyejejfjkd")
longest_palindrome("bartarcarracecarbartar")
longest_palindrome("3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982")