Palindromic Substrings

MediumString DP · Expand Around Centre🧩 String DP LeetCode #647 ↗Updated Oct 30, 2026

Problem

Count how many contiguous substrings of s are palindromes. Substrings are counted by position, so equal text at different start/end indices counts more than once.

Inputs = "abc"Output3 (a, b, c)

Inputs = "aaa"Output6 (a, a, a, aa, aa, aaa)

1 ≤ s.length ≤ 1000 · lowercase English letters

Try it yourself

Java

class Solution {
    public int countSubstrings(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Each palindrome has exactly one centre (a char or the gap between two chars). Expanding outward from each of the 2n-1 centres, every successful step is one new palindrome — so just count the steps.

PatternString DP

Instinct Two strings compared char by char (match, edit, interleave) means dp[i][j] over prefixes; one string's palindromes or splits means dp[l][r] or dp[i].

Memory hack Match? Go diagonal. Mismatch? Ask the neighbours. Up drops a char from s, left drops one from t, diagonal uses both.

Open the String DP guide →

Approaches

Brute ForceTest Every Substring

Time O(n³)Space O(1)

Enumerate all n(n+1)/2 index pairs (i, j) and check each window with two pointers moving inward. Add one for every palindrome.

Java

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

private boolean isPalindrome(String s, int l, int r) {
    while (l < r) {
        if (s.charAt(l++) != s.charAt(r--)) return false;
    }
    return true;
}

Straightforward, but re-checks the same inner characters over and over.

Better2-D Palindrome Table

Time O(n²)Space O(n²)

s[i..j] is a palindrome iff its ends match and the middle s[i+1..j-1] is one (or is shorter than 2). Filling rows from the bottom up makes the middle answer available in O(1), so each pair costs constant time.

Java

public int countSubstrings(String s) {
    int n = s.length(), count = 0;
    boolean[][] pal = new boolean[n][n];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = i; j < n; j++) {
            if (s.charAt(i) == s.charAt(j) && (j - i < 3 || pal[i + 1][j - 1])) {
                pal[i][j] = true;
                count++;
            }
        }
    }
    return count;
}

Removes the cubic re-checking at the price of an n×n table.

OptimalExpand Around Every Centre

Time O(n²)Space O(1)

For each index run two expansions, (c, c) and (c, c+1). While the ends match, the current window is a palindrome — count it and widen by one on each side. Stop at the first mismatch, because every wider window around that centre would contain it.

Java

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

// Number of palindromes centred at (l, r).
private int expand(String s, int l, int r) {
    int found = 0;
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        found++;
        l--;
        r++;
    }
    return found;
}

Dry runs = "abc"

l leftr right changed

c=0 odd
a
l r
a

a

"a" → count=1
c=0 even
a
l
a
r
a

"aa" → count=2
c=1 odd
a
l
a

a
r
a, aaa → count=4
c=1 even
a

a
l
a
r
"aa" → count=5
c=2 odd
a

a

a
l r
"a" → 6 ✔

Quadratic time, constant memory and tiny code — the standard answer.

Pro tip

Manacher's algorithm gets this to O(n) by summing (radius+1)/2 over its radius array — a nice follow-up mention.

At a glance

Level	Approach	Time	Space
Brute Force	Test Every Substring	`O(n³)`	`O(1)`
Better	2-D Palindrome Table	`O(n²)`	`O(n²)`
Optimal	Expand Around Every Centre	`O(n²)`	`O(1)`

Common pitfalls

Counting distinct palindrome strings instead of positions — "aaa" is 6, not 3.
Dropping even-length centres — undercounts strings like "aa".
Filling the table top-down by i — pal[i+1][j-1] is not ready yet.

Interview tips

Ask whether duplicates by position count — it decides the whole approach.
Reuse the centre-expansion helper from Longest Palindromic Substring and say so.
State the bound: at most n(n+1)/2 palindromes, so output-driven O(n²) is natural.

Pattern

Expand around centre → count or find contiguous palindromes without extra memory.

My notes saved in this browser