How do I find the longest palindrome in a string?

  • The challenge:




    Make a function that finds the longest palindrome inside a string.




    Note: This is a question. Please do not take the question and/or answers seriously. More information here.


    If you couldn't tell, this is another trolling problem, although with less explanation than the last.

    Sadly, "a string" doesn't have any palindromes in it at all.

    You're forgetting one-character palindromes.

    So `code-trolling` is my new favorite tag.

    And it only has two questions!

    We've got *two* code-trolling questions on the Hot Network Questions list now!

    Make that 4 questions.

    Why didn't you verb?

    Hmmm. While the first [code-trolling] question was amusing, I cannot help but feel that these questions will really decrease the quality of this site if you guys are not careful. These questions are easy to make and easy to answer poorly, and I can see these getting old very, very fast. Just my 2 cents.

    @JoeZ Don't forget zero character palindromes.

    @Reid Very true. The initial question also attracted a lot of too-obvious, zero-effort answers. We're currently discussing the standards of code-trolling answers in the meta. I personally think that about 30% of the answers even to this question aren't acceptable (including grc's "racecar" solution), although people are starting to make the effort to create more meaningful answers.

    @hippietrail: It's a "How do I " meme.

    @MarkReed "a string" does have many palindromes in it, namely "a", " ", "s", "t", "r", "i", "n", "g" and "".

    So, did you now edit the question for no other purpose than to bring it back up to the front page? How trolling! Sorry, but now I have no choice but to upvote.

    What? No, I just thought the title was bad. I didn't even remember that editing questions bumped them up.

    I actually think this would be a good code golf question.

    You can make the code-golf version, if you want to.

    Code-trolling is in the process of being removed, as per the official stance. This question is very highly voted with many answers, many of which are highly voted. It recieved just slightly over 50% "delete" votes on the poll, but it is unique in that it recieved so many answers and votes, so I am locking it for historical significance.

  • thwd

    thwd Correct answer

    7 years ago

    Go



    The following solution in Go employs the hidden powers of concurrency, closures and recursivity to find the longest palindrome inside a given string:



    func lp(s string) string {
    for i, l := 0, len(s); i < l; i++ {
    if s[i] != s[l-i-1] {
    a, b := make(chan string), make(chan string)
    go func() {
    a <- lp(s[:l-1])
    }()
    go func() {
    b <- lp(s[1:])
    }()
    c, d := <-a, <-b
    if len(c) > len(d) {
    return c
    }
    return d
    }

    }
    return s
    }


    Additionally, it relies entirely on language primitives and built-in types – no standard library – that's how you recognize true quality software.



    You might want to turn your thread, memory and stack size limits up a bit for larger input strings – this is because this solution is so fast that your OS will get all jealous on it.



    Edit – Perks:




    • totally useless on multibyte character strings.

    • will not omit punctuation or whitespace characters.

    • omits upper/lower-case equality.

    • runs in a hard to calculate time – very slow, though.

    • spawns lots and lots of goroutines, depending upon input.

    • gets killed for memory exhaustion after couple of seconds on my machine with over 16000 2049186 goroutines spawned for the input "345345ABCDEabcde edcbaDEABC12312123"


License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM

Tags used