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';
}
}