← All coding problems
Palindromic Substrings
mediumStrings+20 XPTime limit 3s
Count how many substrings of s are palindromes. Substrings at different positions count separately, even if they are equal (in aaa there are 6: a, a, a, aa, aa, aaa).
Input: one line s (lowercase letters).
Output: the number of palindromic substrings.
Constraints: 1 ≤ length of s ≤ 2000.
Think about it: expand around every centre and count each successful expansion. Checking every substring separately is O(n³) — too slow for the big tests.
Sample input 1
abc
Sample output 1
3
Sample input 2
aaa
Sample output 2
6
📖 Stuck? Learn the pattern
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).