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';
}
up vote 11 down vote accepted

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';
    }
}
  • How should I know when to declare a function static ? – coder Sep 20 at 9:11
  • If you don't intend a function to be used by any other translation unit (≅ implementation file), then it's a good candidate for the anonymous namespace or static. – Toby Speight Sep 20 at 9:15

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.

  • A further improvement is to start center from the middle of the input string and work towards both ends - you can stop when there aren't enough characters before the end to accommodate a longer palindrome than your current best. That does make the code longer, but some of that can be reduced again when you eliminate duplication. – Toby Speight Sep 19 at 16:37
  • This is the insight that people are really looking for during an interview. – Tilo Sep 19 at 17:56

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...
}

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

New contributor
Calak is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.