Methods to further reduce time complexity of this algorithm for Longest Palindromic Substring problem

Question

first time poster here so apologies if there are any issues with my post/question. Please let me know so I can adjust.

I'm looking for some help on further improving my solution for the Longest Palindromic Substring found on LeetCode, as it always goes TLE during submission. I think the algo is correct and is around O(N^2), which I think is what I should have but apparently it is still too slow.

Source of my headaches: https://leetcode.com/problems/longest-palindromic-substring

I'm not sure what other practices I can use to optimize it. I don't think DP is something I can use with my implementation as well. But I could be wrong! Also, maybe equal method of std::string is O(N)? But I feel like that isn't something I can alter from my solution.

Any feedback is appreciated!

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length()<2) 
            return s;
        int max=0;
        string p=s;
        int curr_pos=0;
        for(;curr_pos<s.length();curr_pos++){
            for(int i=max+1;i+curr_pos<=s.length();++i){
                string curr_s=s.substr(curr_pos,i);
                if(equal(curr_s.begin(), curr_s.begin() + curr_s.size()/2, curr_s.rbegin())){
                    p=curr_s;
                    max=curr_s.length();
                    i=max;
                }
            }
        }
        return p;
    }
};

Answer 1

Your solution seems to be O(n^3) in the worst case.

You could use DP and store the previously calculated palindromes in a table. Fill the table in increasing order of substring lengths. A string is a palindrome if the first and last characters are the same and the string with its first and last characters stripped was a palindrome.

The complexity of this is O(n^2).

Here is my implementation:

string longestPalindrome(string s) {
    vector table(s.size(), vector<bool>(s.size()));
    string_view sol{s.data(), 1};

    for (size_t i = 0; i < s.size(); ++i)
        table[i][i] = true;
    for (size_t i = 0; i < s.size() - 1; ++i) {
        auto cell = table[i][i+1];
        cell = s[i] == s[i+1];
        if (cell && sol.size() < 2)
            sol = {&s[i], 2};
    }
    for (size_t len = 3; len < s.size(); ++len) {
        for (size_t i = 0; i < s.size() - len + 1; ++i) {
            size_t last = i + len - 1;
            auto cell = table[i][last];
            cell = table[i+1][last-1] && s[i] == s[last];
            if (cell && len > sol.size())
                sol = {&s[i], len};
        }
    }

    return string(sol);
}