Count Palindromic Substrings

Hard ⏱ 18 min 31% acceptance ★★★★★ 4.9
Write count_palindromic_substrings(s) that returns the total number of substrings of s (including single characters) that are palindromes. Use the "expand around center" technique: every palindrome has a center (a single character, or the gap between two characters), so try expanding outward from each of the 2 * len(s) - 1 possible centers.

Examples

Example 1
Input
s = 'aaa'
Output
6
Explanation

Palindromic substrings: 'a', 'a', 'a', 'aa', 'aa', 'aaa' = 6 total.

Example 2
Input
s = 'abc'
Output
3
Explanation

Only the three single characters are palindromes; no longer substring matches.

Constraints

  • 0 <= len(s) <= 1000

Topics

StringsPalindromes

Companies

GoogleMetaAirbnb

Hints

Hint 1

For each index i, expand around center i (odd-length palindromes) and around the gap between i and i+1 (even-length palindromes).

Hint 2

Every successful expansion step counts one more palindrome.

← Parse a Log Line Without Regex Longest Palindromic Substring →
Loading the Python runtime… Run executes your code and shows printed output; Submit checks your function against this problem's examples.