Palindromic Substrings

The key idea

Every palindrome has a center: either a single character (odd length) or the gap between two characters (even length). A string of length n has 2n - 1 such centers. Expand outward from each center while the two ends match, and count one palindrome for every successful expansion.

Problem

Given a string s, return the number of palindromic substrings in it. A substring is a contiguous sequence of characters within the string. A string is a palindrome when it reads the same backward as forward. Substrings at different start or end positions are counted as separate occurrences even when their characters are identical.

Constraints

1 <= s.length <= 1000
s consists of lowercase English letters.

Examples

Input: s = "abc" Output: 3

Input: s = "aaa" Output: 6

Complexity

Time: O(n^2) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →