647. Palindromic Substrings

Counting palindromes looks like it needs a nested scan plus a palindrome check on every substring — an ugly $O(n^3)$. The fix is to stop testing substrings and start growing them from the middle, which is the same expand-around-center idea that shows up across dynamic programming problems about strings.

The problem

Given a string s, count how many of its substrings are palindromes. Substrings at different positions count separately even if they spell the same thing, so overlaps are all counted. (Full statement on LeetCode.)

For "aaa" the answer is 6: three single letters, two "aa" pairs, and the full "aaa".

Intuition: every palindrome has a center

A palindrome is symmetric, so it’s defined entirely by its middle. Walk outward from that middle and it reads the same in both directions — that’s what makes it a palindrome in the first place. So instead of asking “is this substring a palindrome?” for all $O(n^2)$ substrings, flip it around: sit at a center and keep expanding as long as the characters on both sides match. Every successful expansion is one more palindrome, so you count as you go.

The one catch is that palindromes come in two flavors. Odd-length ones like "aba" have a single character at the center; even-length ones like "abba" sit between two characters. So each position gives you two centers to try — the character itself, and the gap just after it. With $n$ single-character centers and $n-1$ gap centers, that’s $2n - 1$ centers total, and each expansion is at most $O(n)$:

$\text{total palindromes} = \sum_{\text{centers}} (\text{expansion length}) = O(n^2)$

Solution

For each center, expand outward and count one palindrome per matching pair. The expand helper handles both flavors — you just hand it either one index (odd) or two adjacent ones (even).

class Solution {
    public int countSubstrings(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            count += expand(s, i, i);      // odd length: center on one char
            count += expand(s, i, i + 1);  // even length: center between two chars
        }
        return count;
    }

    // Grow outward while both sides match; each match is another palindrome.
    private int expand(String s, int left, int right) {
        int found = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            found++;
            left--;
            right++;
        }
        return found;
    }
}

The even case seeds right = i + 1, so when i is the last index the bounds check fails immediately and it contributes nothing — no special-casing needed.

If an interviewer wants the classic table form, dynamic programming also works. Let dp[i][j] mean “s[i..j] is a palindrome”; it’s true when the ends match and the inside dp[i+1][j-1] was already true. Fill it by increasing length so the smaller span is ready first:

class Solution {
    public int countSubstringsDP(String s) {
        int n = s.length(), count = 0;
        boolean[][] dp = new boolean[n][n];
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                // ends match, and the interior is a palindrome (or too short to have one)
                if (s.charAt(i) == s.charAt(j) && (len <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    count++;
                }
            }
        }
        return count;
    }
}

Same $O(n^2)$ time, but it spends $O(n^2)$ memory on the table — which is why expand-around-center is the one I’d reach for.

Complexity

Approach	Time	Space
Expand around center	$O(n^2)$	$O(1)$
Dynamic programming	$O(n^2)$	$O(n^2)$

Both are $O(n^2)$ in the worst case, but they don’t do the same work: the DP always fills all $O(n^2)$ table cells, while center expansion stops the instant a center’s two sides stop matching — so on typical inputs it compares far less, and it never stores anything but a counter.

In an interview

Lead with the reframe: “rather than check every substring, I expand from each center.” That single sentence gets you off the $O(n^3)$ brute force and shows you saw the symmetry. The trap is forgetting even-length palindromes — candidates who only expand from single characters silently miss half the answers, and "aa" returning 2 instead of 3 is the tell. Mention the two center types before you write the loop and you’ve defused it.

If the DP table comes up, it’s the same recurrence as Longest Palindromic Substring — that problem tracks the widest expansion instead of counting them, so the two are worth learning as a pair. To be precise about labels: the table form is interval DP over a 2D dp[i][j], while expanding around a center is really a two-pointer technique, not DP at all — both are worth having next to the string problems in the dynamic programming hub.

References

• LeetCode 647 — Palindromic Substrings