Find longest Palindrome substring I am preparing for technical interview and I found this question on geeksforgeeks, but I did not understand their solution. So, I have written my own solution. I want to optimize this code.

#include &lt;iostream&gt;
#include &lt;string&gt;

bool isPalindrome(std::string&amp; str)
{
    for (int i = 0, j = str.length()-1; i&lt;j; ++i, --j)
    {
        if (str[i] != str[j])
        {
            return false;
        }
    }
    return true;
}

int longestPalindrome(std::string&amp; str, std::string&amp; palindromeStr)
{
    int max = 0, start = 0, end = 0;
    for (int i = 0; i &lt; str.length(); ++i)
    {
        for (int j = i+1; j &lt; str.length(); ++j)
        {
            std::string sub = str.substr(i, j);
            if (isPalindrome(sub) &amp;&amp; max &lt; sub.length())
            {
                max = sub.length();
                start = i;
                end = j;
            }
        }
    }
    palindromeStr = str.substr(start, end);
    return max;
}

int main()
{
    std::string str = "forgeekskeegfor";
    std::string palindromeStr;
    std::cout &lt;&lt; longestPalindrome(str, palindromeStr) &lt;&lt; '\n';
    std::cout &lt;&lt; palindromeStr &lt;&lt; '\n';
}
The code is reasonably clear and obvious, but has some severe inefficiencies.

First, let's pick up some simple oversights.  Both isPalindrome() and longestPalindrome() ought to have internal linkage (using either the static keyword or the anonymous namespace), and the str arguments should be reference to const:

namespace {
    bool isPalindrome(const std::string&amp; str);
    int longestPalindrome(const std::string&amp; str, std::string&amp; palindromeStr);
}


In passing, we can simplify the interface of longestPalindrome().  It doesn't need to return the string and its length; if we simply return the longest palindrome, then obtaining the length is trivial:

    std::string longestPalindrome(const std::string&amp; str);

    // main() can now look like:
    //   std::string palindromeStr = longestPalindrome(str);
    //   std::cout &lt;&lt; palindromeStr.size() &lt;&lt; '\n';
    //   std::cout &lt;&lt; palindromeStr &lt;&lt; '\n';


The next oversight is that std::string::length() returns a std::size_t, so don't compare it with (signed) int:

for (std::size_t i = 0, j = str.length()-1; i&lt;j; ++i, --j)
//   ^^^^^^^^^^^


Note that I've left a bug there (that's neatly missed because we always call this with a non-empty string): if str.length() is zero, then j starts at a very large positive value (because the subtraction is unsigned, and wraps).

BTW, there's a neat way to test a string for symmetry (at the expense of repeating the initial comparisons), using &lt;algorithm&gt;:

static bool isPalindrome(const std::string&amp; str)
{
    return std::equal(str.begin(), str.end(), str.rbegin());
}




Now to the matter of efficiency.  We're creating new string objects for every possible substring of the input.  That's a lot of copying.  We could reduce that by using std::string_view.

That's only part of the way towards an efficient solution, though.  We really need to change the algorithm.  My recommendation is to iterate over each character as a possible mid-point of an embedded palindrome, and at each position, determine what's the longest palindrome possible from there (in most cases, it will be 1 or 2 chars).  There's no need to consider longer substrings centred on that position once you have a failing case, so that eliminates much of the unnecessary work we're doing here.

Hint: for this we can use std::make_reverse_iterator() and std::mismatch().



Finally, the single test we have in main() isn't really enough.  At a minimum, we want examples of odd- and even-length palindromes, and also check that we handle the trivial case of empty string as input.



Update - using iterators

I've developed the idea I hinted at in the second section; there's probably a little more scope for reducing duplication:

#include &lt;algorithm&gt;
#include &lt;iostream&gt;
#include &lt;iterator&gt;
#include &lt;string&gt;
#include &lt;string_view&gt;

namespace
{
    template&lt;typename Iter&gt;
    // requires BidirectionalIterator(Iter)
    void updateBest(Iter forward_start,
                    Iter forward_end,
                    std::reverse_iterator&lt;Iter&gt; backward_start,
                    std::reverse_iterator&lt;Iter&gt; backward_end,
                    std::string_view&amp; best_so_far)
    {
        auto span = std::mismatch(forward_start, forward_end,
                                  backward_start, backward_end);
        auto start = span.second.base();
        auto end = span.first;
        std::string_view candidate{ &amp;*start, static_cast&lt;std::size_t&gt;(std::distance(start, end)) };
        if (candidate.size() &gt; best_so_far.size()) {
            best_so_far = candidate;
        }
    }

    std::string_view longestPalindrome(const std::string&amp; str)
    {
        std::string_view best_so_far;

        // Work out from the middle of the string
        auto const halfway = (str.size() + 1) / 2;

        // first, loop from midpont to end of string (but we can stop
        // when there's no room for a bigger palindrome)
        for (auto i = str.begin() + halfway;  i + best_so_far.length()/2 &lt; str.end();  ++i) {
            // test for odd-length palindrome
            updateBest(i, str.end(),
                       std::make_reverse_iterator(i), str.rend(),
                       best_so_far);
            // test for even-length palindrome
            updateBest(i + 1, str.end(),
                       std::make_reverse_iterator(i), str.rend(),
                       best_so_far);
        }

        // then, loop from midpont to beginning of string (but stop
        // when there's no room for a bigger palindrome)
        for (auto i = str.rbegin() + halfway;  i + best_so_far.length()/2 &lt; str.rend();  ++i) {
            // test for odd-length palindrome
            updateBest(i.base(), str.end(),
                       i, str.rend(),
                       best_so_far);
            // test for even-length palindrome
            updateBest(i.base(), str.end(),
                       i + 1, str.rend(),
                       best_so_far);
        }

        return best_so_far;
    }

}


int main()
{
    for (std::string s: { "",
                "forgeekskeegfor",
                "abc abc",
                "forgeeksskeeg",
                "geeksskeegfor" }) {
        auto palindromeStr = longestPalindrome(s);
        std::cout &lt;&lt; "Found palindrome of length " &lt;&lt; palindromeStr.size()
                  &lt;&lt; " in " &lt;&lt; s &lt;&lt; ": " &lt;&lt; palindromeStr &lt;&lt; '\n';
    }
}