longest_palindromic_substring.cpp

#include <algorithm>
#include <string>

class Solution {
public:
    std::string longestPalindrome(const std::string& s) const {
        std::size_t longest{0};
        std::string::const_iterator longest_begin, longest_end;
        // The search will start at the center of a potential palindrome
        // and work outward to find the length.
        for (auto center_iter = s.begin(), end_iter = s.end(); center_iter < end_iter;) {
            // Accounts for repeated characters in the center
            // e.g. cabbac
            auto forward_start =
                std::find_if_not(center_iter, s.end(),
                                 [character = *center_iter](char c) { return c == character; });
            // Works outward until the characters no longer match
            auto [begin, end] = std::mismatch(std::make_reverse_iterator(center_iter), s.rend(),
                                       forward_start, s.end());
            std::size_t size = end - begin.base();
            if (size > longest) {
                longest = size;
                longest_begin = begin.base();
                longest_end = end;
                // If the distance to the end is less than or equal to the radius of the current
                // longest palindrome, there is no point in continuing.
                end_iter = s.end() - (longest / 2 + 1);
            }
            center_iter = forward_start;
        }
        return {longest_begin, longest_end};
    }
};