Find longest Palindrome substring

Question

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 <iostream>
#include <string>

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

int longestPalindrome(std::string& str, std::string& palindromeStr)
{
    int max = 0, start = 0, end = 0;
    for (int i = 0; i < str.length(); ++i)
    {
        for (int j = i+1; j < str.length(); ++j)
        {
            std::string sub = str.substr(i, j);
            if (isPalindrome(sub) && max < 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 << longestPalindrome(str, palindromeStr) << '\n';
    std::cout << palindromeStr << '\n';
}

Answer 1

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& str);
    int longestPalindrome(const std::string& str, std::string& 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& str);

    // main() can now look like:
    //   std::string palindromeStr = longestPalindrome(str);
    //   std::cout << palindromeStr.size() << '\n';
    //   std::cout << palindromeStr << '\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<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 <algorithm>:

static bool isPalindrome(const std::string& 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 <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <string_view>

namespace
{
    template<typename Iter>
    // requires BidirectionalIterator(Iter)
    void updateBest(Iter forward_start,
                    Iter forward_end,
                    std::reverse_iterator<Iter> backward_start,
                    std::reverse_iterator<Iter> backward_end,
                    std::string_view& 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{ &*start, static_cast<std::size_t>(std::distance(start, end)) };
        if (candidate.size() > best_so_far.size()) {
            best_so_far = candidate;
        }
    }

    std::string_view longestPalindrome(const std::string& 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 < 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 < 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 << "Found palindrome of length " << palindromeStr.size()
                  << " in " << s << ": " << palindromeStr << '\n';
    }
}

Answer 2

You can avoid checking every string by growing the substring on both ends. That way you can quit the inner for loop as soon as the substring isn't a palindrome anymore and use the previous iteration's substring as the palindrome.

if(input_str.empty())return 0;
size_t largest = 1; //if string is not empty then the first character is always a palindrome.
size_t start = 0;
std::string_view view = input_str; //create string view to avoid casting each substr call.
for (int center = 1; center < str.length(); center++)
{
    //even length palindromes
    for (int j = 1; center - j >= 0 && center + j < str.length(); j++)
    {
        if (center - j < 0 || center + j >= str.length() || !isPalindrome(view.substr(center - j, center + j)))
        {
            int length = 2*(j-1);
            if(length > largest){
                start = center - j;
                largest = length;
            }
            break;
        }
    }

    //odd length palindromes
    for (int j = 1; center - j >= 0 && center + j + 1 < str.length; j++)
    {
        if (center - j < 0 || center + j + 1 >= str.length() || !isPalindrome(view.substr(center - j, center + j + 1)))
        {
            int length = 2*(j-1) + 1;
            if(length > largest){
                start = center - j;
                largest = length;
            }
            break;
        }
    }
}

Also I use std::string_view to pass to isPalindrome to avoid allocating a new strings every time. std::string_view creates a view into the string and taking the substring of it is a constant time operation with no allocations.

Answer 3

I suppose that a little optimization could be done by changing the way the substrings are extracted from the main string: the iterations should start from the original string itself and then continue by subtracting characters.

In this way the first time isPalindrome() returns true, the palindrome is the longest one.

Here is a little edit to your longestPalindrome function:

int longestPalindrome(std::string& str, std::string& palindromeStr)
{
    for (int len = str.length(); len > 1; len--)  // One-char strings can't be considered as palindromes...
    {
        for (int j = 0; j <= str.length() - len; j++)
        {
            std::string sub = str.substr(j, j + len);
            if (isPalindrome(sub))
            {
                palindromeStr = sub;
                return len;
            }
        }
    }
    return 0; // It is not a palindrome...
}

Answer 4

I suggest restricting to one loop, flatting the rest. I used the C++17's feature "If statement with initializer" to limit the scope of the variable "current".

#include <algorithm>
#include <iostream>
#include <string>
#include <string_view>

bool is_palindrome(std::string_view str) {
    return std::equal(str.cbegin(), str.cbegin() + str.size()/2, str.crbegin());
}

std::string_view longest_palindrome(std::string_view str)
{
    auto offset = str.cbegin();
    auto size = str.size();

    while(size > 0) {
        if (std::string_view current = {offset, size}; is_palindrome(current)) return current;
        if (offset + size >= str.cend()) { offset = str.cbegin(); --size; }
        else ++offset;
    }
    return {};
}

int main()
{
    for (std::string str: { "", "forgeekskeegfor", "abc abc", "forgeeksskeeg", "geeksskeegfor", "kayak" }) {
        auto palindrome = longest_palindrome(str);
        std::cout << "Found palindrome of length " << palindrome.size()
            << " in " << str << ": " << palindrome << '\n';
    }
}

Test online