mediumDynamic Programming 2DPure DSA~28 min
Count Palindromic Fragments
Auditing a serialized log, you need the total number of contiguous fragments that are palindromes — every individual character counts, and longer symmetric runs count too.
Problem
Given a string s, return the number of palindromic substrings in it. Substrings starting and ending at different indices count separately even if they consist of the same characters.
Input
A string s of length [1, 1000].
Output
An integer: the count of palindromic substrings.
Constraints
- 1 <= s.length <= 1000
- s consists of lowercase English letters.
Examples
Example 1
Input
s = "abc"
Output
3
Each single character: 'a','b','c'.
Example 2
Input
s = "aaa"
Output
6
'a' x3, 'aa' x2, 'aaa' x1 = 6.