647. Palindromic Substrings

Edited by Charles

Medium · Python · Dynamic Programming

Problem

Read the original problem on LeetCode.

The official page contains the problem statement, examples, and constraints.

Explanation, examples & other approaches

Core idea

Given a string s, return the total number of palindromic substrings in s.

A palindrome reads the same forward and backward.

Original study notes follow, including intermediate snippets and earlier attempts.

Idea

Given a string s, return the total number of palindromic substrings in s.

A palindrome reads the same forward and backward.

For example:

s = "aaa"

The palindromic substrings are:

"a"
"a"
"a"
"aa"
"aa"
"aaa"

Therefore, the answer is 6.

This problem is different from many previous subsequence DP problems because defining something like

dp[i] = number of palindromes ending at i

does not give us a clear recurrence.

Instead, we use the key property of a palindrome:

A substring s[i:j+1] is a palindrome if its two end characters are equal and its inner substring s[i+1:j] is also a palindrome.

This naturally leads to a 2D DP solution.

Dynamic Programming

State Definition

Let

dp[i][j]

denote:

Whether the substring s[i:j+1] is a palindrome.

The interval is inclusive on both sides:

[i, j]

So:

dp[i][j] = True

means s[i:j+1] is a palindromic substring.

Initialization

Initially, set every state to False.

dp = [[False] * len(s) for _ in range(len(s))]

We should not assume any substring is a palindrome before checking it.

State Transition

There are two main cases.

Case 1: s[i] != s[j]

If the two end characters are different, the substring cannot be a palindrome.

Therefore:

dp[i][j] = False

Since the DP table is initialized to False, no update is needed.

Case 2: s[i] == s[j]

If the two end characters are equal, there are three situations.

Situation 1: Single Character

If

i == j

then the substring contains only one character.

Every single character is a palindrome.

For example:

"a"

Situation 2: Two Characters

If

j - i == 1

and

s[i] == s[j]

then the substring is also a palindrome.

For example:

"aa"

Situation 3: Length Greater Than 2

If

j - i > 1

and the two end characters are equal, then we only need to check whether the inner substring is a palindrome.

That is:

dp[i + 1][j - 1]

So:

dp[i][j] = dp[i + 1][j - 1]

when

s[i] == s[j]

Combined Transition

if s[i] == s[j]:
    if j - i <= 1:
        dp[i][j] = True
    elif dp[i + 1][j - 1]:
        dp[i][j] = True

Whenever dp[i][j] becomes True, we have found one palindromic substring, so increment the result.

res += 1

Why Is j - i <= 1 a Special Case?

Consider:

i == j

The substring has length 1, so it is automatically a palindrome.

Now consider:

j - i == 1

The substring has length 2.

If:

s[i] == s[j]

then it is also automatically a palindrome.

For these cases, there is no meaningful inner substring s[i+1:j] to check.

Therefore:

j - i <= 1

is handled directly.

Traversal Order

This is the most important part of this DP solution.

For longer substrings, we use:

dp[i + 1][j - 1]

to calculate:

dp[i][j]

So before computing dp[i][j], the state

dp[i + 1][j - 1]

must already be known.

Notice that dp[i + 1][j - 1] lies below and to the left of dp[i][j] in the DP table.

Therefore, i must be traversed from bottom to top:

for i in range(len(s) - 1, -1, -1):

For each i, j moves from left to right:

for j in range(i, len(s)):

Traversal order:

i: bottom -> top
j: left -> right

This guarantees that dp[i + 1][j - 1] has already been computed.

Example

s = "aaa"

The DP table corresponds to substrings s[i:j+1].

i = 2

s[2:3] = "a"

Single character:

dp[2][2] = True

Count:

res = 1

i = 1

For:

s[1:2] = "a"

we get:

dp[1][1] = True

For:

s[1:3] = "aa"

since:

s[1] == s[2]

and the length is 2:

dp[1][2] = True

Now:

res = 3

i = 0

For:

s[0:1] = "a"

dp[0][0] = True

For:

s[0:2] = "aa"

dp[0][1] = True

For:

s[0:3] = "aaa"

the end characters are equal:

s[0] == s[2]

and the inner substring:

s[1:2] = "a"

is a palindrome because:

dp[1][1] = True

Therefore:

dp[0][2] = True

Final result:

6

Complexity Analysis

Time Complexity

O(n²)

We examine every possible substring interval [i, j].

Space Complexity

O(n²)

A 2D DP table is used.

Summary

State Definition

dp[i][j] = whether s[i:j+1] is a palindrome

Initialization

dp = [[False] * len(s) for _ in range(len(s))]

State Transition

if s[i] == s[j]:
    if j - i <= 1:
        dp[i][j] = True
    elif dp[i + 1][j - 1]:
        dp[i][j] = True

Whenever:

dp[i][j] == True

increment the palindrome count.

Traversal Order

i: from right to left
j: from i to right

Final Answer

Total number of states dp[i][j] that become True

Common Mistakes

1. Do not define the DP state only using one index.

   The palindrome property depends on both ends of a substring, so a 2D state is much more natural:

dp[i][j]

1. Do not forget the special cases:

j - i <= 1

These represent substrings of length 1 or 2.

1. When the substring length is greater than 2, checking only

s[i] == s[j]

is not enough.

You must also check:

dp[i + 1][j - 1]

1. The traversal order is crucial.

Since:

dp[i][j]

depends on:

dp[i + 1][j - 1]

i must be traversed from right to left.

1. A substring must be continuous.

This problem counts palindromic substrings, not palindromic subsequences.

Study record

Field	Value
Attempts	1
Mastery	❚
The Latest Attempt	August 12, 2026

Python solution

class Solution:
    def countSubstrings(self, s: str) -> int:
        l = len(s)

        dp = [[False] * l for _ in range(l)]
        res = 0

        for i in range(l - 1, -1, -1):
            for j in range(i, l):
                if s[i] == s[j]:
                    if j - i <= 1:
                        res += 1
                        dp[i][j] = True
                    elif dp[i + 1][j - 1]:
                        res += 1
                        dp[i][j] = True

        return res

---

Back to Day 40 Dynamic Programming XIII · All Algorithm notes