Write a function that returns the longest palindrome in a given string

Question

e.g "ccddcc" in the string "abaccddccefe"

I thought of a solution but it runs in O(n^2) time

Algo 1:

Steps: Its a brute force method

1. Have 2 for loops
   for i = 1 to i less than array.length -1
   for j=i+1 to j less than array.length
2. This way you can get substring of every possible combination from the array
3. Have a palindrome function which checks if a string is palindrome
4. so for every substring (i,j) call this function, if it is a palindrome store it in a string variable
5. If you find next palindrome substring and if it is greater than the current one, replace it with current one.
6. Finally your string variable will have the answer

Issues: 1. This algo runs in O(n^2) time.

Algo 2:

1. Reverse the string and store it in diferent array
2. Now find the largest matching substring between both the array
3. But this too runs in O(n^2) time

Can you guys think of an algo which runs in a better time. If possible O(n) time

Answer 1

You can do it in linear time. There's a description of the algorithm here - http://johanjeuring.blogspot.com/2007/08/finding-palindromes.html

Answer 2

i think, the first solution is O(n ^ 3). I think, you are forgetting, ispalindrome itself is O(n) and you are doing that for all the substrings? Am I missing something here?

Answer 3

I was asked this question recently. Here's the solution I [eventually] came up with. I did it in JavaScript because it's pretty straightforward in that language.

The basic concept is that you walk the string looking for the smallest multi-character palindrome possible (either a two or three character one). Once you have that, expand the borders on both sides until it stops being a palindrome. If that length is longer than current longest one, store it and move along.

// This does the expanding bit.
function getsize(s, start, end) {
    var count = 0, i, j;
    for (i = start, j = end; i >= 0 && j < s.length; i--, j++) {
        if (s[i] !== s[j]) {
            return count;
        }
        count = j - i + 1; // keeps track of how big the palindrome is
    }
    return count;
}

function getBiggestPalindrome(s) {
    // test for simple cases
    if (s === null || s === '') { return 0; }
    if (s.length === 1) { return 1; }
    var longest = 1;
    for (var i = 0; i < s.length - 1; i++) {
        var c = s[i]; // the current letter
        var l; // length of the palindrome
        if (s[i] === s[i+1]) { // this is a 2 letter palindrome
            l = getsize(s, i, i+1);
        }
        if (i+2 < s.length && s[i] === s[i+2]) { // 3 letter palindrome
            l = getsize(s, i+1, i+1);
        }
        if (l > longest) { longest = l; }
    }
    return longest;
}

This could definitely be cleaned up and optimized a little more, but it should have pretty good performance in all but the worst case scenario (a string of the same letter).

Answer 4

Here's one that I came up with but it's not that good: "Yo, be tall, lace. Help pay apple!" He call. - Late boy.

It's actually pretty easy to make a palindrome without using a computer program. This one took me about 30-45 minutes to make. I'm just an amateur.