5. Longest Palindromic Substring

Brute-force

class Solution {
public:
    string longestPalindrome(string s)
    {
        int n = s.size();
        for (int j = n; j > 0; --j)
        {
            for (int i = 0; i <= n - j; i++)
            {
                if (isPalindrome(s.substr(i, j)))
                {
                    return s.substr(i, j);
                }
            }
        }
        return "";
    }

    bool isPalindrome(string s)
    {
        int i = 0, j = s.size() - 1;
        while (i < j)
        {
            if (s[i] != s[j])
            {
                return false;
            }
            ++i; --j;
        }
        return true;
    }
};

• T: $O(N^3)$
• S: $O(1)$

Expand From Centers

class Solution {
public:
    string longestPalindrome(string s)
    {
        string res = "";
        int curLen = 0, maxLen = 0;
        for (int i = 0; i < s.size(); ++i)
        {
            int left = i, right = i;
            while (left >= 0 && right < s.size() && s[left] == s[right])
            {
                curLen = right - left + 1;
                if (curLen > maxLen)
                {
                    res = s.substr(left, curLen);
                    maxLen = curLen;
                }
                --left; ++right;
            }

            left = i, right = i + 1;
            while (left >= 0 && right < s.size() && s[left] == s[right])
            {
                curLen = right - left + 1;
                if (curLen > maxLen)
                {
                    res = s.substr(left, curLen);
                    maxLen = curLen;
                }
                --left; ++right;
            }
        }
        return res;
    }
};

• T: $O(N^2)$
• S: $O(1)$

Manacher’s Algorithm

class Solution {
public:
    string longestPalindrome(string s)
    {
        string t = "#";
        for (char c : s)
        {
            t += c;
            t += "#";
        }

        int n = t.size();

        vector<int> p(n, 0);

        int center = 0, radius = 0;

        for (int i = 0; i < n; i++)
        {
            int mirror = 2 * center - i;

            if (i < radius)
            {
                p[i] = min(radius - i, p[mirror]);
            }

            while (i + 1 + p[i] < n && i - 1 - p[i] >= 0 && t[i + 1 + p[i]] == t[i - 1 - p[i]])
            {
                p[i]++;
            }

            if (i + p[i] > radius)
            {
                center = i;
                radius = i + p[i];
            }
        }

        int maxLen = 0;
        int centerIndex = 0;
        for (int i = 0; i < n; i++)
        {
            if (p[i] > maxLen)
            {
                maxLen = p[i];
                centerIndex = i;
            }
        }

        int startIndex = (centerIndex - maxLen) / 2;

        return s.substr(startIndex, maxLen);
    }
};

• T: $O(N)$
• S: $O(N)$