Palindromic Substrings

1. Problem & Core Objective

Count how many palindromic substrings the string contains. Substrings at different positions count separately even if identical.

s = "abc"    →  3      "a", "b", "c"
s = "aaa"    →  6      "a", "a", "a", "aa", "aa", "aaa"

Constraints: 1 <= s.length <= 1000 · lowercase letters

What's actually being tested: that this is question 5 with one line changed — count each successful expansion instead of tracking a maximum. The reusability is the point; if the centre framing was understood, this is nearly free.

2. First-Principles Thought Process

Every expansion step is one palindrome

Expanding from a centre, each time the characters match you've found a palindrome — one character wider than the last.

"aaa", centre at index 1:
    "a"    (lo=1, hi=1)   → 1 palindrome
    "aaa"  (lo=0, hi=2)   → 1 more

So instead of recording the widest, count each successful step.

Why positional duplicates count

"aaa" contains three separate "a" substrings — at indices 0, 1 and 2. They're identical as strings but distinct as substrings, and the problem counts substrings.

That's exactly what centre-expansion produces naturally: each centre is a different position, so each contributes its own count. No deduplication needed — and any attempt to deduplicate would be wrong.

The count for a run of k identical characters

A block of k identical characters contributes k(k+1)/2 palindromes — every contiguous sub-block is one. For "aaa" that's 3 × 4 / 2 = 6 ✓, which matches the expected output and is a useful sanity check.

Both parities again

n character-centres and n − 1 gap-centres. Omitting the even case undercounts every even-length palindrome — "aa" would be missed entirely.

3. Solution Paths

Approach 1 — Check every substring (brute force)

public int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++)
        for (int j = i; j < s.length(); j++)
            if (isPalindrome(s, i, j)) count++;
    return count;
}

• Time O(n³) · Space O(1)

Counter-questions on this approach

⭐ "Why is this worse than for the longest-palindrome question?"

It isn't worse — it's the same O(n³). But here there's no early-exit opportunity at all: the longest-substring version could prune substrings shorter than the current best, whereas counting must examine every single one.

So the pruning that made the cubic version tolerable there doesn't exist here.

"Is 10^9 actually too slow at n = 1000?"

n²/2 substrings times O(n) each is about 5 × 10^8 character comparisons — borderline, likely a timeout in Java. The expansion version is 10^6.

Approach 2 — DP table

public int countSubstrings(String s) {
    int n = s.length(), count = 0;
    boolean[][] isPal = new boolean[n][n];

    for (int i = n - 1; i >= 0; i--)                 // i descending: i+1 must be ready
        for (int j = i; j < n; j++) {
            if (s.charAt(i) == s.charAt(j) && (j - i < 3 || isPal[i + 1][j - 1])) {
                isPal[i][j] = true;
                count++;
            }
        }
    return count;
}

• Time O(n²) · Space O(n²)

Counter-questions on this approach

⭐ "Why does i descend here rather than iterating by length?"

Because isPal[i][j] reads isPal[i+1][j-1] — a larger first index. Descending i guarantees row i+1 is already complete.

Iterating by increasing length also works and is arguably clearer about the dependency. Both are valid fill orders; what matters is that the dependency is satisfied, and stating which one you're relying on is worth doing.

⭐ "What does j - i < 3 cover?"

Lengths 1, 2 and 3 — all of which need no interior check. A single character is trivially a palindrome; a pair needs only its two characters equal; a triple needs only its ends equal, since the middle character is always palindromic.

Without it, a length-2 interval would read isPal[i+1][i], an inverted range holding a meaningless default false — so "aa" would be missed.

"Same time as expansion but O(n²) space. Why show it?"

Because it's the answer this section is nominally about, and because the table becomes genuinely useful when queried repeatedly — Palindrome Partitioning again. For a single count it's over-built.

Approach 3 — Expand around centre, counting (optimal)

public int countSubstrings(String s) {
    int count = 0;
    for (int i = 0; i < s.length(); i++) {
        count += expand(s, i, i);          // odd-length centres
        count += expand(s, i, i + 1);      // even-length centres
    }
    return count;
}

private int expand(String s, int lo, int hi) {
    int found = 0;
    while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) {
        found++;                            // each successful match is one palindrome
        lo--; hi++;
    }
    return found;
}

Trace — s = "aaa":

• Time O(n²) · Space O(1)

Counter-questions on this approach

⭐ "What's the one-line difference from the longest-palindrome version?"

expand returns a count of successful steps instead of the final width. The caller sums instead of taking a max.

Everything else — the centre enumeration, both parities, the loop guard — is identical. That's the point of establishing the centre framing in question 5.

⭐ "Why does counting each expansion step give the right total?"

Because each successful match produces a palindrome that's exactly two characters wider than the previous one from that centre, and every palindrome has exactly one centre.

So summing over all centres counts every palindromic substring exactly once. No double-counting is possible, because two different centres produce palindromes at different positions.

⭐ "\"aaa\" has three identical \"a\" substrings. Should they count separately?"

Yes — the problem counts substrings, which are identified by position, not by content. The three single as are at indices 0, 1, 2 and are three distinct substrings.

Centre-expansion handles this correctly without effort, since each centre is a different position. Deduplicating by string content would be wrong and would give 3 instead of 6.

Worth confirming rather than assuming, because "count the palindromic substrings" could plausibly mean distinct ones.

"Sanity-check the total for a run of identical characters."

A block of k identical characters has k(k+1)/2 palindromic substrings — every contiguous sub-block. For "aaa", 3 × 4 / 2 = 6 ✓, matching the expected output.

That's a good independent check on the implementation, since it's derived from combinatorics rather than from the algorithm.

"Worst case?"

All identical characters — every centre expands fully, giving O(n²) matches. At n = 1000 the answer is 500,500, and the work is about 10^6 steps.

Comparison

4. Why the Optimal Wins

Same reasoning as question 5, with one addition: the cubic version can't even be pruned here, because counting requires examining every substring rather than stopping at the best.

Expansion counts each palindrome exactly once as it's discovered, with no table and no deduplication.

The framing worth keeping:

Each successful expansion step IS a palindrome. Count them instead of tracking the widest — one line different from finding the longest.

And the check worth carrying: a run of k identical characters contributes k(k+1)/2, which validates the implementation independently.

5. Java Prerequisites

Counting expansion

private int expand(String s, int lo, int hi) {
    int found = 0;
    while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) { found++; lo--; hi++; }
    return found;
}

Both parities — expand(i, i) and expand(i, i + 1).

DP fill order — isPal[i][j] reads isPal[i+1][j-1], so either descend i or iterate by increasing length.

j - i < 3 covers lengths 1–3, which need no interior check.

6. Interview Communication Guide

Clarifying questions: Do identical substrings at different positions count separately (yes — this is the definition of substring)? Is a single character a palindrome (yes)? Contiguous (yes — subsequences would be a different problem)?

The pitch

"This is the longest-palindrome question with one line changed.

The same observation applies: every palindrome has a centre, either a character for odd lengths or a gap for even ones, giving 2n − 1 centres. From each I expand outward while characters match.

The difference is what I do with each successful step. For the longest, I tracked the final width. Here, each successful match is itself a palindrome — one character wider than the previous from that centre — so I count them and sum over all centres.

That counts every palindromic substring exactly once, because every palindrome has exactly one centre and different centres sit at different positions.

Worth confirming: identical substrings at different positions do count separately. 'aaa' has three single-a substrings at indices 0, 1 and 2, and the expected answer is 6, not 3. Centre-expansion gets this right without effort — deduplicating by content would be wrong.

A useful independent check: a run of k identical characters contributes k(k+1)/2 palindromes, since every contiguous sub-block is one. For 'aaa' that's 6, which matches.

O(n²) time, O(1) space. The DP table is also O(n²) time but O(n²) space, and here the cubic brute force can't even be pruned — counting requires examining every substring rather than stopping at the best."

Edge cases to volunteer:

Name "aa". It must give 3, not 2 — the two singles plus the pair. Missing the even-centre expansion gives 2, and missing positional duplicates gives 2 as well, so it catches both errors.

7. Follow-Up Questions — Modified Constraints

⭐ "Count DISTINCT palindromic substrings."

Genuinely different — now content matters, not position. Collect the found substrings in a HashSet, which is O(n²) strings of O(n) length each, so O(n³) space in the worst case. A palindromic tree (Eertree) does it in O(n) and is the proper answer at scale.

⭐ "Return the longest instead of the count."

That's question 5 — track the maximum width rather than summing. Same traversal, different accumulator, which is the whole relationship between these two questions.

"Count palindromic subsequences instead."

LeetCode 730. No centres to expand from, since subsequences aren't contiguous. It's an O(n²) interval DP with careful inclusion–exclusion for repeated characters — substantially harder.

"What if n were 10^5?"

O(n²) is 10^10 — too slow. Manacher's computes every centre's maximum radius in O(n), and the count is then the sum of radii. That's the linear answer.

"Count palindromic substrings of exactly length k."

Stop each expansion once the width reaches k and count only that one. O(nk) — faster than the general count when k is small.

"What if the string had 10^6 characters but only two distinct letters?"

The alphabet size doesn't help — "abababab…" has O(n) palindromes while "aaaa…" has O(n²). The output itself can be quadratic, so no algorithm counts them faster than the answer's magnitude unless it counts without enumerating, which Manacher's does.