Count the palindromic substrings of a string

Count the substrings of a string that are palindromes. Substrings at different positions count separately even when they spell the same text.

Interface

Unless you agree on a different interface with the interviewer, assume:

• count_substrings(s: str) -> int

Example

count_substrings("abc")   ->  3   # "a", "b", "c"
count_substrings("aaa")   ->  6   # "a" x3, "aa" x2, "aaa"
count_substrings("abba")  ->  6   # "a", "b", "b", "a", "bb", "abba"

Constraints

• 1 <= len(s) <= 1000; lowercase letters.
• Target O(n^2) time and O(1) extra space.

Clarifying questions

• Do repeated substrings at different positions count separately?
• Do single characters count?
• How long can the string be? (Above about 10^5, quadratic is too slow.)

What a strong answer covers

• The brute force (check every substring, O(n^3)) as the baseline.
• Expand around every centre: 2n - 1 centres (each character and each gap), growing outward while the ends match and counting each step. O(n^2) time, O(1) space.
• The O(n^2) dynamic-programming table is_pal[i][j] as an alternative, and why it uses more memory.
• Manacher's algorithm for O(n) if pushed.
• Tests: one character, all equal characters, no repeated characters.

Follow-ups

• Return the longest palindromic substring.
• Count only distinct palindromic substrings.
• Count palindromic subsequences instead of substrings.