Count Palindromic Substrings

Reported in interviews at Akuna Capital Opendoor

Problem statement

Given a string $s$, return the number of palindromic substrings in it. A substring is a contiguous sequence of characters; two substrings with different start or end indices count separately even if they are equal as strings.

Constraints:

  • $1 \le \mathrm{len}(s) \le 1000$
  • $s$ consists of lowercase English letters.

Examples:

  • $s = $ "abc" $\to 3$ (each single character: "a", "b", "c").
  • $s = $ "aaa" $\to 6$ ("a", "a", "a", "aa", "aa", "aaa").
Show hint

Instead of listing substrings and testing each, what single point is every palindrome built symmetrically around?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems