Find palindrome in a string

The purpose of this code is to find the largest palindrome in a string. It works fine when the string is short, but every time I test this code with 1000+ characters in a string, it takes forever to give me the palindrome in it.

```
PalindromeFinder::PalindromeFinder(){}

string PalindromeFinder::toString(){

stringstream ss;
ss
getLargestPalindromeFound();
ss getSizeOfLargestPalindromeFound();
return ss.str();
}

string PalindromeFinder::getLargestPalindromeFound(){
return this->largestPalindromeFound;
}

int PalindromeFinder::getSizeOfLargestPalindromeFound(){
return this->largestPalindromeFound.length();
}

string str="djclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjssssssevessssssfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjfdjclsodjf";

truncateToLargestPalindrome(str);

void PalindromeFinder::truncateToLargestPalindrome(string& inputString){

string empty="";

inputString.erase(remove_if(inputString.begin(), inputString.end(), ::isspace), inputString.end());

inputString.erase(rem

Let's see how your code computes out...

You loop for every position in the input string. Then, you find each possible string starting from there. So, for 1000 characters, that's 1000 + 999 + 998, etc. Which turns out to be \$\frac{1000^2}{2}\$ - or a half-million strings that you check.

Now, for each of those string values, you then check to see if they are a palindrome. Presumably, for each of those strings, in the isPlaindrome method, you compare the string to the reverse of the string, which means checking each character again.

That's another few iterations of each string, meaning your code ends up with a complexity in the order of cubic: \$O(N^3)\$.

Shavings

Now, there's ways to improve the code quite easily, for example, there's no point in checking (or even substringing) anything that's shorter than the current longest palindrome. In other words, why test 5 letter substrings if you've already found a 6 letter one? That will reduce the work you do, but, it will still be pretty slow.

Creating a string instance for each candidate is also not a great solution - you should find a way to do the palindrome checking on the original string, without making copies of sub-parts.

Still, I can't help but feel that the better solution is to reduce the computational complexity a lot, which makes scaling the code much better.

Algorithm

My suggestion is to change the algorithm. Your current one checks every possible substring in the input to find a palindrome. A better solution would be to only test strings which are "almost known" to be palindromes.

A palindrome is a word where the last half is a reflection of the first (in terms of letters). This implies that there is a middle of the reflection. If you can start at the middle of the reflection, and work outwards, until the reflection is broken, then you can compare what works with what you have already found, and move on.

Since there are even and odd sized palindromes, there are two types of "middle": two characters at the middle for even, and 1 character for odd sized palindromes.

There can be just one "middle" at each character in the input. If you can determine how wide the palindrome is spanning each middle, then you are one step ahead. At worst case, if the string is entirely 1 letter, like aaaaaaaaaaaaa, then you will have to check a lot of palindromes, and the worst-case performance is \$O(n^2)\$ (which is still a bunch better than your cubic approach). On the other hand, a reasonably random input will typically have mostly 1-letter palindromes, and they will test out very quickly, so a best-case complexity is just \$O(n)\$

I took the liberty of writing up a solution using the approach I describe:

std::string largestPalindrome(std::string input) {
    std::string largest = "";
    // offset is O or 1 for odd, and even sized palindromes.
    for (int offset = 0; offset  mid ? mid : max;

            for (int i = 0; i  largest.length()) {
                        largest = input.substr(mid - i, i + i + offset + 1);
                    }
                } else {
                    break;
                }
            }
        }
    }

    return largest;
}

Note, the mid-loop runs only twice (once for even, once for odd). The inner i loop will tend to be pretty small because it only runs while the strings centered on the mid point are actually palindromes.... and large palindromes will be the exception, not the rule.

There's only 1 big loop, in other words.

Additionally, substr is only called when there's a larger palindrome than previously seen... it's an uncommon call.

The above code runs the example str input in 3 milliseconds on my computer (and you can see it running in ideone too)

StackExchange Code Review Q#105072, answer score: 7