Palindromic Substrings is one of the most important String Dynamic Programming problems.

You are given:

string s

Goal:

Count all palindromic substrings present in the string. 

A palindrome:

Reads the same forward and backward. 

Example

s = "aaa" 

Output:

6 

Explanation:

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

Total:

6 

Key Observation

Every palindrome satisfies:

First character = Last character 

And:

Inner substring must also be palindrome. 

DP State:

Inner substring must also be palindrome. 

Transition:

s[i] == s[j] and (j - i < 2 or dp[i+1][j-1]) 

Approach 1 : Memoization

Explanation

For every substring:

1. Check matching ends.
2. Check inner substring.
3. Store result.
4. Reuse calculations.

Approach 2 : Tabulation

Explanation

State:

dp[i][j] = Palindrome status

If:

 s[i] == s[j]

and:

Length <= 2 or dp[i+1][j-1]

Then:

dp[i][j] = true 

Increase answer count.

Dry Run

Input:

s = "aaa"

DP Table:

a
a
a
aa
aa
aaa 

Count:

6 

Answer:

 6

Approach 3 : Expand Around Center

Explanation

Every palindrome has a center.

Possible centers:

Character Center or Gap Center 

Expand outward while:

left == right 

Count every valid palindrome.

Practice

Dynamic ProgrammingTime Complexity: O(n²)Space Complexity: O(n²)

Expand Around Center
Time Complexity: O(n²)
Space Complexity: O(1)

Every palindrome has a center.

Expand Around Center uses O(1) space and is preferred.