gistfile1.txt

For an arbitrary string, detect the largest palindrome* present within it.
* a sequence of characters the same forwards and backwards at least 3 characters long.

For instance in "abbabcdedc", the longest palindrome would be "cdedc".

Answers?

Do you have a target time complexity? (that's how I would hedge in an interview :))

No, I just wanted to give a problem I didn't have an answer to. I thought it would be fun to work through it together. I think the complexity should be around O(n^2) though.

My instinct is that you start by finding center candidates -- either successive identical character pairs ('xx', a[n] == a[n+1]) or by 3-character palindromic sequences ('yxy', a[n] == a[n+2]). I think that's one O(n) pass.

Then you grow those sequences as long as the character to the left of your sequence is the same as the character to the right of your sequence. I don't know what the time complexity of that is. Drop those results in a maxheap in O(lg n), return max result in O(1).

HIRED!

haha, want me to delete that comment so other people can guess without my pre-disposing them?

Up to you, I just wanted to see what other people thought. Was the question too silly?

…

On 2012-03-24, at 15:08, Oliver ***@***.*** wrote: haha, want me to delete that comment so other people can guess without my pre-disposing them? --- Reply to this email directly or view it on GitHub: https://gist.github.com/2188292

It's pretty Computer Science-y. I thought it might be NP-hard. Looks like there's a linear time solution http://en.wikipedia.org/wiki/Longest_palindromic_substring

not too efficient but short:

def largest_palindrome(s)
  (s.split /\s/).map {|x| x.length}.max.downto(1).each do |x|
    re = ("(\\w)" * x) + "\\w?"
    x.downto(1).each { |y| re += "\\#{y}" }
    s.match(re) { |z| return z }
  end
end

Here's something in Haskell. I tried to decompose the problem into 1. make substrings, 2. filter out non palindromes, then 3. find the longest string. substrings time complexity grows like a Trianglular number. I think palindrome and longest are both O(n).

Usage: longest (palindromes "abbabcdedc")

    substrings []     = []
    substrings (x:xs) = decTail (x:xs) ++ substrings xs
      where
        decTail []       = []
        decTail (y:ys)   = [y] : [ (y:z) | z <- decTail ys ]

    longest []     = []
    longest (w:ws) = if length w > length w' then w else w' where w' = longest ws

    palindromes w = [ s | s <- substrings w, s == reverse s ]