A stretch of a string is a non-empty run of consecutive characters, s[i..j] with i <= j. Write count_palindromes(s: str) -> int that returns how many stretches of s read the same forwards and backwards.
Stretches are counted by position, not by content: in "aaa" the three single "a"s are three different stretches.
count_palindromes("abc") # 3 "a", "b", "c"
count_palindromes("aaa") # 6 "a" x3, "aa" x2, "aaa"
count_palindromes("abba") # 6 "a", "b", "b", "a", "bb", "abba"
count_palindromes("racecar") # 10 7 single letters, "cec", "aceca", "racecar"
Constraints:
1 <= len(s) <= 3000scontains only lowercase English letters
Checking every stretch on its own is O(n³). Aim for O(n²) time; O(1) extra space is possible.
Show hint
if s[i..j] is a palindrome, then s[i-1..j+1] is one exactly when s[i-1] == s[j+1]. So every palindrome grows out of a shorter one around the same middle.