LeetEye LeetEye
Medium 1D Dynamic Programming ~5 min

Palindromic Substrings

1d-dp palindromic-substrings

Problem

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

A string is a palindrome when it reads the same backward as forward.

A substring is a contiguous sequence of characters within the string.

Examples

Example 1
Input: s = "abc"
Output: 3
"a", "b", "c" (each single char is a palindrome)
Example 2
Input: s = "aaa"
Output: 6
"a" (3 times), "aa" (2 times), "aaa" (1 time)
Key Insight

Same as Longest Palindromic Substring: expand around each center, but COUNT instead of track max.

Expand from each of 2n-1 centers. Each successful expansion = one more palindrome. Sum all counts.

How to Approach This Problem

Pattern Recognition: When you see keywords like palindromic substrings 1d-dp, think 1D Dynamic Programming.

Step-by-Step Reasoning

1 Each single character is:
Answer: Always a palindrome
Any single character reads same forwards and backwards.
2 When expanding from center and s[left] == s[right]:
Answer: Found one palindrome, continue expanding
Each successful expansion is a NEW palindrome. "a", "aba", "cabac" are all different palindromes from same center.
3 Palindromic substrings in "aba":
Answer: 4
"a" (pos 0), "b", "a" (pos 2), "aba" = 4 palindromes.
4 The expand function should return:
Answer: Count of palindromes found
Each expansion step = one palindrome. Return total count from this center.
5 Total palindromes = sum of:
Answer: Palindromes from each odd center + even center
Try all 2n-1 centers, sum up palindromes found from each.

Solution

def countSubstrings(s: str) -> int:
    count = 0
    
    def expand(left, right):
        nonlocal count
        while left >= 0 and right < len(s) and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1
    
    for i in range(len(s)):
        expand(i, i)      # Odd length
        expand(i, i + 1)  # Even length
    
    return count

Complexity Analysis

Time O(n²)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice 1D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye