5. Longest Palindromic Substring

Hint - Brute-force

class Solution {
public:
    string longestPalindrome(string s)
    {
        // Start with the longest possible substring and reduce the length until we find a palindrome
        for ()
        {
            // Check all substrings of length 'j'
            for ()
            {
                // If the substring s.substr(i, j) is a palindrome, return it as the result
                if ()
                {
                }
            }
        }
        // If no palindrome is found (which is unlikely since single characters are palindromes), return an empty string
    }

    // Helper function to check if a given string 's' is a palindrome
    bool isPalindrome(string s)
    {
        // Initialize two pointers at the start and end of the string
        // Check characters from both ends moving towards the center
        while ()
        {
            // If characters at pointers do not match, it's not a palindrome
            // Move the pointers closer to the center
        }
        // If all characters matched, the string is a palindrome
    }
};

• 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)$

Hint - Expand From Centers

class Solution {
public:
    string longestPalindrome(string s)
    {
        // Initialize the result string to store the longest palindrome found
        // Initialize current length and maximum length of palindrome found

        // Iterate over each character in the string as the center of a potential palindrome
        for ()
        {
            // Case 1: Odd length palindrome with center at 'i'
            // Expand around the center while characters on both sides are equal
            while ()
            {
                // Calculate current palindrome length
                // Update result if a longer palindrome is found
                // Move left pointer to the left and right pointer to the right
            }

            // Case 2: Even length palindrome with centers at 'i' and 'i+1'
            // Expand around the centers while characters on both sides are equal
            while ()
            {
                // Calculate current palindrome length
                // Update result if a longer palindrome is found
                // Move left pointer to the left and right pointer to the right
            }
        }
        // Return the longest palindromic substring found
    }
};

• 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)$

Hint - Manacher's Algorithm

class Solution {
public:
    string longestPalindrome(string s)
    {
        // Transform the original string to avoid even-length palindrome issues by inserting '#'
        // between every character and at the beginning and end.

        // Length of the transformed string

        // Array to store the length of the palindrome radius for each center

        // Center and radius of the rightmost palindrome found

        for ()
        {
            // Mirror of the current index i with respect to the current center

            // If within the bounds of the current known palindrome, use the mirror's palindrome length

            // Attempt to expand the palindrome centered at i

            // Update the center and radius if the expanded palindrome at i goes beyond the current known radius
        }

        // Find the longest palindrome in the transformed string

        // Calculate the start index of the longest palindrome in the original string

        // Return the longest palindrome substring from the original string
    }
};

• 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)$