Skip to content

Instantly share code, notes, and snippets.

@joshbuddy
Created March 24, 2012 21:39
Show Gist options
  • Save joshbuddy/2188292 to your computer and use it in GitHub Desktop.
Save joshbuddy/2188292 to your computer and use it in GitHub Desktop.
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?
@onewland
Copy link

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

@joshbuddy
Copy link
Author

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.

@onewland
Copy link

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).

@joshbuddy
Copy link
Author

HIRED!

@onewland
Copy link

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

@joshbuddy
Copy link
Author

joshbuddy commented Mar 24, 2012 via email

@onewland
Copy link

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

@aghull
Copy link

aghull commented Mar 24, 2012

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

@luciferous
Copy link

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 ]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment