Count of Palindromic Substrings

Mechanism

A palindromic substring is uniquely identified by its center and how far it extends symmetrically before a mismatch — so instead of checking all O(n²) substrings for the palindrome property (an O(n) check each), you walk outward from every one of the 2n−1 possible centers (n single-character centers, n−1 between-character centers for even-length palindromes) and stop the moment the two sides disagree or a pointer runs off the string. Every expansion step that succeeds identifies exactly one more palindromic substring, so counting is free — it falls out of the expansion itself.

Recognize the pattern

• Task mentions "palindromic substrings" (contiguous), not subsequences.
• You need a count or list of all palindromic substrings, or the longest one.
• Any correct answer must account for both odd-length palindromes (single middle character, e.g. "bdb") and even-length ones (middle is a gap, e.g. "dd").
• String length is small-to-moderate (≤ 1000–5000) — a hint that O(n²) is the expected ceiling, not that O(n) Manacher is required.

Brute force → optimal

Brute force: enumerate all O(n²) substrings (i, j) and test each for palindrome-ness in O(n). Total: O(n³) time, O(1) extra space.

Optimal — expand around center: for each of the 2n−1 centers, expand outward while characters match. Each expansion does O(n) work in the worst case (all characters equal, e.g. "aaaa"), so total work is still O(n²) time in the worst case, but O(1) extra space and no substring materialization or re-comparison — every character pair is compared at most once per valid radius, with no wasted re-scans of already-confirmed substrings the way brute force does.

Complexity, derived

Time: there are 2n−1 centers. For center k, the expansion can run at most min(k+1, n−k) steps before hitting a string boundary — summing the maximum possible radius over all centers gives Σ O(n) = O(n²) in the worst case (e.g. a string of all identical characters, where every expansion goes to the boundary). Best case (no repeated adjacent characters, e.g. "abcde") each expansion stops after O(1) steps, giving O(n) total.

Space: O(1) beyond the input and a counter — no DP table needed for the counting variant (a 2-D `dp[i][j]` table achieves the same O(n²) time but costs O(n²) space, so center-expansion strictly dominates it for this problem).

Traced example — "cddpd" (indices c0 d1 d2 p3 d4)

All 2n−1 = 9 centers are accounted for (5 odd + 4 even); 3 of the 4 even centers contribute nothing because their immediate neighbors already mismatch. Total distinct expansions yielding matches: c, d, dd, d, p, dpd, d = 7, matching the expected output.

Java — expand around center

public int countSubstrings(String s) {
    int n = s.length(), count = 0;
    for (int center = 0; center < 2 * n - 1; center++) {
        int l = center / 2;
        int r = l + center % 2;   // even center: r = l+1, odd center: r = l
        while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
            count++;
            l--;
            r++;
        }
    }
    return count;
}

Pitfalls

• Forgetting even-length centers — only iterating n odd centers undercounts (e.g. misses "dd").
• Off-by-one when mapping a single `center` index to (l, r): the `center/2, center/2 + center%2` trick is easy to get backwards.
• Confusing an out-of-bounds pointer with a character mismatch — they both stop expansion, but only a mismatch involves comparing two actual characters; an out-of-bounds stop means one side has run off the string entirely.
• Re-scanning substrings already confirmed as non-palindromic in a naive DP fill order (must fill by increasing substring length, not by (i,j) row order, if you use the `dp[i][j]` table).
• Confusing this with counting distinct palindromic substrings — this problem counts every occurrence (positions), not unique strings.

When to use / when not — trade-offs

Use expand-around-center when you need a simple, O(1)-space O(n²) solution and n is at most a few thousand. Use the DP table (`dp[i][j]` = is s[i..j] a palindrome) when you also need to query palindrome-ness of arbitrary ranges repeatedly after one O(n²) preprocessing pass — expand-around-center doesn't give you that lookup structure. Use Manacher's algorithm when n is large (10⁵+) and true O(n) time is required — it eliminates the redundant re-expansion work by reusing previously computed radii via palindrome symmetry, at the cost of noticeably higher implementation complexity (transformed string, mirror-index bookkeeping) and no accuracy or simplicity benefit for small n.

Takeaways

• 2n−1 centers (n odd + n−1 even) is the key insight that unifies odd/even palindrome handling into one loop — a correct trace must account for all of them, even the ones that contribute zero matches.
• Counting is a side-effect of expansion — no separate verification step needed, unlike brute force.
• O(n²) time / O(1) space is optimal for interview purposes; Manacher's O(n) is the named alternative for large-n constraints.
• An all-equal string is the worst case for both count and time: "aaa" has 6 palindromic substrings (3+2+1 = n(n+1)/2), and every center expands all the way to the boundary.

Recall: Why does expanding around 2n−1 centers correctly capture every palindromic substring exactly once, with no duplicates and none missed?

Pattern derived from classic center-expansion technique for palindrome substring problems (Manacher's algorithm as the linear-time alternative); worked example based on the given problem's test cases.