0

I am writing some code to find the longest palindrome in a string. I want to start at index 0 and then push the increasing length of the substring to an array:

ex:
string = "ababa"
[["a", "b"], ["a", "b", "a"], ["a", "b", "a", "b"], ["a", "b", "a", "b", "a"]] 

It should then start on index 1 and do the same:

ex:
string = "ababa"
[["b","a"],["b","a","b"],["b","a","b","a"]

This should continue until the index is length -1 .However, the following code stops after it has gone through all iterations beginning with the first index and only returns:

[["a", "b"], ["a", "b", "a"], ["a", "b", "a", "b"], ["a", "b", "a", "b", "a"]]

What is the flaw in my logic? Code below

def longest_palindrome(s)
  array = s.chars
  start = 0
  place = 1
  output = []
  while start < s.length - 1
    while place < s.length
      output << array[start..place]
      place += 1
    end
  start += 1
  end
return output  
end  
3
  • 1
    If I'm understanding correctly, you want to reset variable place to something like place = start + 1 if start + 1 < s.length. Reset outside of the inner while loop, so around where you increment up start
    – philip yoo
    Aug 11, 2016 at 3:06
  • Thanks this works! I do not understand why my code was not working though. After it goes through the inner while loop the first time it will return to the start of the outer loop with values start = 1 and place = 1 and then go through the inner loop again is the problem when start becomes 2 and the first iteration of the inner while loop becomes array[2..1]?
    – John
    Aug 11, 2016 at 3:32
  • I made a small mistake. You should reset place after you increment start. So first do start += 1, and then you should do place = start + 1 if (start + 1) < s.length
    – philip yoo
    Aug 11, 2016 at 3:41

2 Answers 2

0

I believe this is what you are after:

def longest_palindrome(s)
  arr = s.chars
  output = []

  (0...s.length).each do |start|
    (start + 1...s.length).each do |place|
      output << arr[start..place]
    end
  end

  output
end

longest_palindrome("ababa")
 => [["a", "b"], ["a", "b", "a"], ["a", "b", "a", "b"], ["a", "b", "a", "b", "a"], ["b", "a"], ["b", "a", "b"], ["b", "a", "b", "a"], ["a", "b"], ["a", "b", "a"], ["b", "a"]] 

Using iterators really simplifies things. Here is a more concise version:

def longest_palindrome(s)
  output = (0...s.length).flat_map do |start|
    (start + 1...s.length).map do |place|
      s[start..place]
    end
  end
end

longest_palindrome("ababa")
 => ["ab", "aba", "abab", "ababa", "ba", "bab", "baba", "ab", "aba", "ba"] 
0

A working, non-optimized, written on-the-fly 30 minutes, who knows how awfully slow longest palindrome finder:

def longest_palindrome(string, min_size = 2)
  string = string.downcase # we will not be taking 
  return string if string == string.reverse # skip all calculaions of the passed string itself is a palindrome in original order
  letters = string.chars # Convert string to array of bytes
  combinations = [] # Initialize all letter combinations
  (min_size..letters.size).each do |n| # min_size is the shortest length a palindrome is allowed to be, default 2
    combinations.concat(letters.combination(n).to_a) # concat all combinations for n amount of characters in the string
  end
  palindromes = [] # Initialize array for all palindromes
  combinations.each do |combo| # interate every combo
    combo.size.times do # for every letter ordering is done via size of this letter combo
      palindromes << combo.dup if combo == combo.reverse # add to list of palindromes if the combinations is the same backwards
      combo.rotate! # rotate the letters for next order checking
    end
  end
  palindromes.sort {|a, b| a.size <=> b.size }.last.join # sort the palidromes by length, take the biggest one, and return it as a full string
end

p longest_palindrome("racecar") #=> racecar
p longest_palindrome("applesauce") #=> pecep
p longest_palindrome("madam im adam") #=> mada m adam
p longest_palindrome("madamimadam") #=> madamimadam

but it works, sort of. As you can see if sort of gets odd when spaces/puncuation are added to the mix. You can always clean the string of it in the first line if need be.

Viva la algorithmless coding!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.