1167. Count Palindromic Substrings (DP)

Given a string s, count the number of palindromic substrings (contiguous), counting different positions separately even when the content is identical. The input is JSON {s}.

Input: JSON {s}.

Output: Integer — the number of palindromic substrings.

Examples

Input: {"s":"abc"}
Output: 3
Explanation: Three single characters.

Input: {"s":"aaa"}
Output: 6
Explanation: a, a, a, aa, aa, aaa.

Input: {"s":"ab"}
Output: 2
Explanation: Two single characters.

Constraints

• 1<=|s|<=1000

Asked by