What is the brute force approach and complexity for Palindromic Substrings?

Test each substring by comparing its ends, then the next pair inside with time complexity O(N^3) and space complexity O(1).

What is the optimal approach and complexity for Palindromic Substrings?

From each of the 2N − 1 centres, grow outward while the ends match with optimal time complexity O(N^2) and space complexity O(1).

How do you identify the pattern for Palindromic Substrings?

Look for key signals in the prompt: "count the palindromic substrings" indicates The answer is a count over every contiguous range, so there are about N² candidates to look at.; "substring (contiguous)" indicates Each candidate is a range s[i..j]. Only its end pairs need to match.; "reads the same backward as forward" indicates The rule is about mirrored pairs: s[i] = s[j], and then the inside must be a palindrome too..

Palindromic Substrings

Medium·LeetCode #647Basic Anchor

LeetCode

Jump:

30-Second Mental ModelPalindrome DP (dp[i][j] for s[i..j]), with centre expansion as the optimal

Complexity:O(N^3)→O(N^2)

Key Insight

Every palindrome has a centre: a letter for odd lengths, or the gap between two letters for even lengths. There are 2N − 1 centres. From each one, move L to the left and R to the right while the ends match. Each match is one palindrome. The first mismatch ends this centre, and no table is needed.

Core Validity Invariant

A range is a palindrome exactly when every pair from its centre outward matches, and the first mismatch ends the palindromes for that centre.

Problem

You are given a string s. Count its palindromic substrings. A substring is a run of letters that sit next to each other in s, and a palindrome reads the same forwards and backwards.

Each substring is counted by its position. If the letter a appears three times, that gives three single-letter palindromes, even though they are the same letter.

Input

A string s of lowercase letters.

Output

The number of substrings of s that are palindromes.

Example 1

Input: s = "abc"

Output: 3

The palindromes are a, b and c. No two letters side by side are equal, so nothing longer works.

Example 2

Input: s = "aaa"

Output: 6

They are a, a, a, aa, aa and aaa. The two aa substrings count separately because they start at different positions.

Constraints

• 1 ≤ s.length ≤ 1000
• s consists of lowercase English letters.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
Is one letter by itself a palindrome? How many substrings does a string of length N have in total?
2.
To check one substring, which pairs of letters must match? Where do the pairs start and end?
3.
If s[l..r] is a palindrome, what must be true about the part inside it, s[l+1..r-1]?
4.
Every palindrome has a middle. Can I list every possible middle, including the gaps between two letters?
5.
If I count the palindromes around each middle by growing outward, can any palindrome be counted twice?

Brute force approach

Idea

Try every substring s[i..j]. Compare the two ends, then the next pair inside them, and so on. If every pair matches, count it. A substring is a palindrome exactly when all of its end pairs match.

Thinking process

1
For abba, take s[0..3] = abba. Compare s[0] = a with s[3] = a: match. Then s[1] = b with s[2] = b: match. No pairs are left, so it is a palindrome.
2
Take s[0..2] = abb. Compare s[0] = a with s[2] = b: they differ, so stop. It is not a palindrome.
3
Every pair (i, j) with i ≤ j is one substring. For abba that is 4 + 3 + 2 + 1 = 10 substrings.
4
Count the ones that pass. For abba the answer is 6: the four single letters, bb and abba.

Visual

Each cell is one substring s[i..j] (row i, column j). Brute force checks it from both ends. Blue = the pair being compared now. Orange = a pair that was already compared inside a longer substring, so the work is repeated. Green = palindrome, red = not.

Brute force: check every substrings = "abba"step 1/18

s[i..j] is a palindrome?

✓

Brute

substring: s[0..0]
substrings checked: 1
palindromes so far: 1
comparisons so far: 0

s[0..0] = "a" is a palindrome

Substring "a" is a palindrome, so the count is now 1.

Code & Implementation

brute.cpp

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        int count = 0;
        // Try every substring s[i..j].
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // Check it from both ends, moving inward.
                bool isPal = true;
                for (int l = i, r = j; l < r; l++, r--) {
                    if (s[l] != s[r]) { isPal = false; break; }
                }
                if (isPal) count++;
            }
        }
        return count;
    }
};

Complexity

Time O(N^3)Space O(1)

There are about N²/2 substrings. Checking one can take up to N/2 pair comparisons, so the total is about N³/4 steps. Only a few counters are stored.

Better approach

Why brute force is slow

The brute force checks the same inner pairs again and again. In abba, the pair s[1], s[2] is compared inside abba and again when bb is checked on its own.

What repeated work are we doing?

Each longer substring re-checks every pair inside it. The inner part of a long substring is compared many times over.

What information can we reuse?

isPal[i+1][j-1] was already decided at a shorter length. So each cell costs one comparison and one lookup, and nothing is checked twice.

New approach

Idea

Store the answer for every substring in a table isPal[i][j]. A substring is a palindrome when its two ends match and the part inside it is a palindrome: isPal[i][j] = s[i] == s[j] && isPal[i+1][j-1]. Fill the table by length, so the inside is always ready before the cell that needs it.

Thinking process

1
For abba, every single letter is a palindrome, so the length-1 cells are all true.
2
Length 2: ab is no, bb is yes (both ends are b, and nothing is inside), ba is no.
3
Length 3: abb is no (a ≠ b), bba is no (b ≠ a).
4
Length 4: abba has equal ends, a = a, and its inside bb is already true. So it is a palindrome. Count the true cells: 4 + 1 + 1 = 6.

Visual

Row = left end i, column = right end j. Cells below the diagonal are never used. A cell reads the cell one step inside it (blue). Green ✓ = palindrome, red ✗ = not. Filled by length 1, then 2, then 3, and so on.

Table: isPal[i][j] by lengths = "aabaa"step 1/16

✓now

Cell

s[i..j]: s[0..0] = "a"
length: 1
palindromes so far: 1

palindrome

Cell (0, 0): a single letter is always a palindrome, so count it.

Code & Implementation

better.cpp

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        int count = 0;
        // isPal[i][j] = is s[i..j] a palindrome?
        vector<vector<bool>> isPal(n, vector<bool>(n, false));
        // Fill by length, so the inside s[i+1..j-1] is always ready before s[i..j].
        for (int len = 1; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                // Lengths 1 and 2 have no inside: only the two ends have to match.
                isPal[i][j] = s[i] == s[j] && (len <= 2 || isPal[i + 1][j - 1]);
                if (isPal[i][j]) count++;
            }
        }
        return count;
    }
};

Complexity

Time O(N^2)Space O(N^2)

There are about N²/2 cells that matter, and each cell does one comparison and one lookup. The table holds N² booleans, which is why the space is O(N²).

Optimized approach

Idea

Start from brute force

Brute force checks each substring from both ends, from scratch. A palindrome grows out of its middle, one matching pair at a time, so growing from each middle finds every palindrome without checking any substring from scratch.

Find the repeated work

The inner pairs of a long substring are checked again for every longer substring that contains them.

Define the state — what variables do I need?

centre: The middle of a palindrome: a letter (odd length) or the gap between two letters (even length). There are 2N − 1 of them.
L, R: The two ends of the current expansion. They start on the centre and move one step outward each time.
count: How many palindromes have been found so far. Each successful step adds one.

Define validity

A range is a palindrome exactly when every pair from its centre outward matches, and the first mismatch ends the palindromes for that centre.

Define the transitions — when does each pointer move, and why is it safe?

For each centre c from 0 to 2N − 2

L = c / 2, R = L + c % 2

Even c is a letter (odd-length palindromes). Odd c is a gap (even-length palindromes). Together they cover every palindrome.

While L ≥ 0, R < N and s[L] = s[R]

count++, then L−−, R++

The ends match, and the range inside them was already a palindrome at the previous step. So the new range is a palindrome too.

The ends differ, or L or R leaves the string

Stop this centre

A longer palindrome with this centre would need this same pair to match, and it does not.

What does the current window add to the answer?

Each successful step adds exactly one palindrome, the range s[L..R] it has just reached. After every centre has been expanded, the count is the answer.

Code & Implementation

optimal.cpp

class Solution {
public:
    int countSubstrings(string s) {
        int n = s.size();
        int count = 0;
        // 2n - 1 centres: n letters, and the n - 1 gaps between neighbouring letters.
        for (int centre = 0; centre < 2 * n - 1; centre++) {
            // Even numbers are letters (odd-length palindromes), odd numbers are gaps (even-length).
            int l = centre / 2;
            int r = l + centre % 2;
            // Grow outward while the ends match. Each match is one new palindrome.
            while (l >= 0 && r < n && s[l] == s[r]) {
                count++;
                l--;
                r++;
            }
        }
        return count;
    }
};

Complexity

Time O(N^2)Space O(1)

There are 2N − 1 centres. Each one expands at most about N/2 steps, so the worst case is O(N²) (all letters the same). Only L, R and the counter are stored.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Test each substring by comparing its ends, then the next pair inside	O(N^3)	O(1)
Better	isPal[i][j] says whether s[i..j] is a palindrome; each cell reads one cell inside it	O(N^2)	O(N^2)
Optimal	From each of the 2N − 1 centres, grow outward while the ends match	O(N^2)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“count the palindromic substrings”The answer is a count over every contiguous range, so there are about N² candidates to look at.
“substring (contiguous)”Each candidate is a range s[i..j]. Only its end pairs need to match.
“reads the same backward as forward”The rule is about mirrored pairs: s[i] = s[j], and then the inside must be a palindrome too.

Substring range s[i..j]+valid = ends match and the inside is valid+count every valid range→Palindrome DP (dp[i][j] for s[i..j]), with centre expansion as the optimal

This is the anchor of the palindrome sub-pattern. A range is a palindrome when its ends match and the range inside it is a palindrome. The table gives every range a cell for that rule, and centre expansion applies the same rule without storing anything. Longest Palindromic Substring uses the same rule but keeps one answer. This problem counts every palindrome, so every matching step adds one to the total instead of only the longest range being kept.

Don't make this mistake

Pattern confusion: only odd-length centres

✗ for (int i = 0; i < n; i++) { int l = i, r = i; while (l >= 0 && r < n && s[l] == s[r]) { count++; l--; r++; } }

✓ for (int centre = 0; centre < 2 * n - 1; centre++) { int l = centre / 2, r = l + centre % 2; while (l >= 0 && r < n && s[l] == s[r]) { count++; l--; r++; } }

Odd-length palindromes have a letter in the middle, but even-length ones have a gap in the middle, and only the right loop visits the gaps. On abba the wrong loop counts 4 (a, b, b, a) and misses bb and abba, so it gives 4 instead of 6. On the dry-run aabaa it gives 7 instead of 9.

Counting once per centre instead of once per match

✗ bool hit = false; while (l >= 0 && r < n && s[l] == s[r]) { hit = true; l--; r++; } if (hit) count++;

✓ while (l >= 0 && r < n && s[l] == s[r]) { count++; l--; r++; }

A centre with a long palindrome holds several palindromes, one for each step outward. On aaa the centre at the middle a gives a and aaa, which is 2, but the wrong version adds 1. The total becomes 5 instead of 6.

Table: forgetting that length 2 has an empty inside

✗ isPal[i][j] = s[i] == s[j] && isPal[i + 1][j - 1];

✓ isPal[i][j] = s[i] == s[j] && (len <= 2 || isPal[i + 1][j - 1]);

aa has nothing inside, so it is a palindrome. But isPal[i+1][i] is never filled, so it reads as false and aa is missed. On aaa the table gives 4 instead of 6, because both aa substrings are missed.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like DP — Strings translate into production architectures and low-level memory mechanics.

LLD Architecture