Palindromic Substrings

How it works

The “expand around center” idea is great, but it can redo the same comparisons many times, making it O(n^2).

Manacher’s Algorithm speeds this up to O(n) by using two tricks:

1. Normalize odd/even palindromes

   • Insert a separator like # between characters:
     "abba" → "#a#b#b#a#"
   • Now every palindrome in this new string has an odd-length center, so we only handle one case.

2. Reuse information using a “current best palindrome window”

   • Maintain a palindrome window [l, r] (the farthest-reaching palindrome found so far).
   • For a new position i inside [l, r], we know its mirror position mirror = l + (r - i).
   • The palindrome radius at i can be at least the smaller of:
     • how much space remains inside the window (r - i)
     • the palindrome radius at mirror (p[mirror])
   • Then we try to expand further only if possible.

This avoids repeated expansions and ensures total work is linear.

Steps

1. Build transformed string t by inserting # between characters and at ends.
2. Create array p where p[i] = radius of palindrome centered at i in t.
3. Track the current palindrome boundaries [l, r].
4. For each index i:
   • If i is inside [l, r], initialize p[i] using its mirror.
   • Expand outward while characters match.
   • If palindrome at i extends beyond r, update [l, r].
5. Convert radii in p into the number of palindromic substrings in the original string:
   • Each center contributes (p[i] + 1) // 2
6. Sum contributions and return res.

Complexity

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

Things to watch for

Forgetting Even-Length Palindromes

When using the expand-around-center approach, many developers only expand from single characters (odd-length centers). Even-length palindromes like "aa" or "abba" require expanding from between two characters, so both (i, i) and (i, i+1) centers must be checked.

Off-By-One Errors in DP Table Indexing

In the DP approach, the recurrence dp[i][j] = dp[i+1][j-1] requires careful iteration order. Processing i from high to low ensures dp[i+1][j-1] is computed before dp[i][j]. Iterating in the wrong direction leads to reading uninitialized values.

Counting Substrings Instead of Counting Once Per Palindrome

Some implementations accidentally count the same palindrome multiple times or miss counting single characters as palindromes. Every single character is itself a palindrome, so the minimum count for a string of length n is n.

class Solution:
    def countSubstrings(self, s: str) -> int:

        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)
        res = 0
        for i in p:
            res += (i + 1) // 2
        return res

class Solution {
public:
    vector<int> manacher(string& s) {
        if (!s.size()) return {};
        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;
    }

    int countSubstrings(string s) {
        vector<int> p = manacher(s);
        int res = 0;
        for (int i : p) {
            res += (i + 1) / 2;
        }
        return res;
    }
};