All problems

Palindromic Substrings

Medium · two pointers

A word is a palindrome if it reads the same forwards and backwards, like "level" or "noon". A single letter counts as a palindrome.

Given a string s, count how many of its substrings are palindromes. A substring is a run of consecutive letters of s. Substrings are counted by position: if the same text appears at two different places in s, each place counts separately.

Return that count.

Examples

Example 1

Input: s = "abc"

Output: 3

Only the single letters "a", "b" and "c" are palindromes.

Example 2

Input: s = "aaa"

Output: 6

Three single "a" substrings, two "aa" substrings (positions 0-1 and 1-2) and one "aaa".

Example 3

Input: s = "abba"

Output: 6

The four single letters, "bb" and "abba".

Constraints