The problem
Given a string s, return how many of its substrings are palindromes. Substrings at different positions count separately, even if they are the same letters.
Examples
01
- Input
s = "abc"
- Output
3
02
- Input
s = "aaa"
- Output
6
Constraints
- 1 ≤ s.length ≤ 1000
- Only lowercase English letters.
The idea
Run Manacher’s algorithm, as in Longest Palindromic Substring, to find for every centre the longest palindrome around it.
Around one centre, every shorter palindrome is the long one with equal amounts trimmed from each end — so a centre whose longest palindrome has length p[i] in s accounts for ⌈p[i] ÷ 2⌉ palindromes (the ⌈ ⌉ means round up). In aaa, the centre on the middle a reaches length 3: “a” and “aaa”, 2 = ⌈3 ÷ 2⌉. Add them up over all centres.
- Time
- O(n)
- Space
- O(n)
Solution · every language run against every case
class Solution: def countSubstrings(self, s: str) -> int: # Manacher's algorithm (see Longest Palindromic Substring): p[i] is the reach of the # longest palindrome centred at i in "#a#b#...#". Every shorter one with the same # centre is a palindrome too, and there are (p[i] + 1) // 2 of them in s. t = "#" + "#".join(s) + "#" n = len(t) p = [0] * n center = right = 0 for i in range(n): if i < right: p[i] = min(right - i, p[2 * center - i]) while i - p[i] - 1 >= 0 and i + p[i] + 1 < n and t[i - p[i] - 1] == t[i + p[i] + 1]: p[i] += 1 if i + p[i] > right: center, right = i, i + p[i] return sum((r + 1) // 2 for r in p)