Longest Palindromic Substring

How it works

Manacher’s Algorithm is an optimized way to find the longest palindromic substring in linear time.

The key ideas are:

• Unify odd and even length palindromes by inserting a special character (like #) between characters.
  • Example: "abba" → "#a#b#b#a#"
• Use previous palindrome information to avoid re-checking characters.
• Maintain a current rightmost palindrome and mirror indices to reuse results.

Instead of expanding from every center independently, Manacher’s algorithm reuses symmetry, making it much faster than the two-pointer approach.

Steps

1. Transform the string
   • Insert # between characters and at both ends to handle odd/even palindromes uniformly.
2. Create an array p[]
   • p[i] = radius of palindrome centered at index i in the transformed string.
3. Maintain two pointers:
   • center - center of the current rightmost palindrome
   • right - right boundary of that palindrome
4. For each index i:
   • If i is inside the current palindrome:
     • Initialize p[i] using its mirror around center
   • Expand around i while characters match
   • If the palindrome expands beyond right, update center and right
5. After processing:
   • Find the index with the maximum value in p
   • Convert that position back to the original string indices
6. Return the longest palindromic substring

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Handling Both Odd and Even Length Palindromes

When expanding around centers, you must check both odd-length palindromes (single character center like "aba") and even-length palindromes (between two characters like "abba"). Forgetting to handle one case means missing valid palindromes. Always expand from both (i, i) and (i, i+1) for each position.

Off-by-One Errors in Substring Extraction

After finding the palindrome boundaries, extracting the correct substring is error-prone. If your left pointer l and right pointer r point to positions just outside the palindrome after expansion, you need to adjust them (e.g., l+1 to r-1) before extracting. Verify your indices with simple test cases like "a" and "aa".

Returning Wrong Result for Single Character Strings

For an input like "a", the longest palindromic substring is "a" itself. If you initialize your result string as empty and only update it when you find a longer palindrome, you might return an empty string for single-character inputs. Ensure your initialization handles this edge case correctly.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def manacher(s):
            t = '#' + '#'.join(s) + '#'
            n = len(t)
            p = [0] * n
            l, r = 0, 0
            for i in range(n):
                p[i] = min(r - i, p[l + (r - i)]) if i < r else 0
                while (i + p[i] + 1 < n and i - p[i] - 1 >= 0
                       and t[i + p[i] + 1] == t[i - p[i] - 1]):
                    p[i] += 1
                if i + p[i] > r:
                    l, r = i - p[i], i + p[i]
            return p

        p = manacher(s)
        resLen, center_idx = max((v, i) for i, v in enumerate(p))
        resIdx = (center_idx - resLen) // 2
        return s[resIdx : resIdx + resLen]

class Solution {
public:
    vector<int> manacher(string& s) {
        string t = "#" + string(1, s[0]);
        for (int i = 1; i < s.size(); ++i)
            t += "#" + string(1, s[i]);
        t += "#";
        int n = t.size();
        vector<int> p(n, 0);
        int l = 0, r = 0;
        for (int i = 0; i < n; i++) {
            p[i] = (i < r) ? min(r - i, p[l + (r - i)]) : 0;
            while (i + p[i] + 1 < n && i - p[i] - 1 >= 0 &&
                   t[i + p[i] + 1] == t[i - p[i] - 1])
                p[i]++;
            if (i + p[i] > r)
                l = i - p[i], r = i + p[i];
        }
        return p;
    }

    string longestPalindrome(string s) {
        vector<int> p = manacher(s);
        int resLen = 0, center_idx = 0;
        for (int i = 0; i < p.size(); i++) {
            if (p[i] > resLen) {
                resLen = p[i];
                center_idx = i;
            }
        }
        int resIdx = (center_idx - resLen) / 2;
        return s.substr(resIdx, resLen);
    }
};