Find longest palindrome in a string (LeetCode problem 5)

Question

The code below is my solution to the following problem (problem #5 on LeetCode):

Given a string s, return the longest palindromic substring in s.

I wonder whether my use of iterators is an overkill. They seem to be convenient for calculating the length of the ranges and for constructing the string in the answer. They also provide a standard way of dealing with an empty range.

I would also like to know whether I am on the right spot with tuples.

Any other comments about the coding style and the idiomatic use of C++ would be greatly appreciated!

class Solution {    
    // Return pair of iterators for the longest polindromic substring
    // starting with i and j as center.
    // The end iterator is one past the end of the range, like in STL.
    // If s[i] != s[j], an empty range is returned.
    // tuple is new in C++17
    tuple<string::const_iterator, string::const_iterator> 
        polindromicRange(const string &s, int i, int j) {
        
        if (j >= s.size() || s[i] != s[j]) return {s.begin(), s.begin()};
        
        string::const_iterator begin = s.cbegin() + i;
        string::const_iterator end = s.cbegin() + j + 1;
        
        while (begin > s.begin() && end < s.end() && *(begin - 1) == *end) {
            --begin;
            ++end;
        };
        
        return {begin, end};
    }
    
    void newLongestRange(const string &s, int i, int j,
                         string::const_iterator &longestBegin,
                         string::const_iterator &longestEnd) {
        auto [begin, end] = polindromicRange(s, i, j);
        if (end - begin > longestEnd - longestBegin) {
            longestBegin = begin; 
            longestEnd = end;
        }
    }
    
public:
    string longestPalindrome(string s) {
        string::const_iterator longestBegin, longestEnd;
        for (int i = 0; i < s.size(); ++i) {
            newLongestRange(s, i, i, longestBegin, longestEnd);
            newLongestRange(s, i, i + 1, longestBegin, longestEnd);
        }
        return string(longestBegin, longestEnd);
    }
};

P.S. The Solution class is a requirement of LeetCode.

Answer 1

Here's C++20 version I would write:

#include <string>
#include <ranges>
#include <iostream>
#include <algorithm>
using namespace std;

template <ranges::input_range R>
auto longestPalindrome(R&& r) {
    auto result = ranges::subrange(r.cbegin(), r.cbegin());
    const int n = ranges::ssize(r);
    for (int i = 0; i < n; ++i) {
        auto [it1, it2] = ranges::mismatch(r | views::drop(i), r | views::reverse | views::drop(n - 1 - i));
        if (ranges::distance(it2.base(), it1) > ranges::ssize(result)) {
            result = ranges::subrange(it2.base(), it1);
        }
        auto [it3, it4] = ranges::mismatch(r | views::drop(i + 1), r | views::reverse | views::drop(n - 1 - i));
        if (ranges::distance(it4.base(), it3) > ranges::ssize(result)) {
            result = ranges::subrange(it4.base(), it3);
        }
    }
    
    return result;
}


int main() {
    
    string a = "dabcba";
    auto res = longestPalindrome(a);
    for (auto c : res) {
        cout << c << ' ';
    }    
}

Demo: https://wandbox.org/permlink/rhpiU2j3011ttECw

I'm not convinced that this answer will be welcomed in job interviews, though.

Pros of this code:

• This is applicable not only to std::string, every range is fit to this algorithm. C-style arrays, std::array, std::vector, std::span every range that satisfies requirements for ranges::input_range can be used.

• The STL algorithm names are self-descriptive. In ranges::mismatch(r | views::drop(i), r | views::reverse | views::drop(n - 1 - i));, you basically checks two range: one range from r[i], one reversed range from r[i], and find the pair where first mismatch happens.

• ranges::subrange does not copy the contents of r, it is just pair of iterators that point to somewhere in r.

Cons:

• Verbose. It is awful that adding using namespace std::ranges; makes this code fail to compile. The verbosity is nature of C++, not particularly nature of this code, though.

• Due to nature of reverse_iterator, omitting .base() in the second return value of ranges::mismatch gives awful error.

Answer 2

With modern C++, I recommend using a view object rather than a pair of iterators. Views are conceptually similar, but have additional semantics - the iterators point into the same object.

C++ comes with std::string_view specifically for strings.

Consider using auto rather than spelling out iterator type for begin and end.

*(begin - 1) is more conventionally written begin[-1].

Slight misspelling in polindromicRange - sounds trivial, but spelling errors can frustrate searching in large sources.

Does longestPalindrome() really need to take a string by value? Accept a const string& or a std::string_view if possible.

In longestPalindrome(), consider starting from the middle of the string and working outwards - we can exit the loop when we get near to the ends of the string, if we already found a longer palindrome than could be present there.