Count palindrome substrings in a string
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a lowercase ASCII string s, count the number of substrings that are palindromes and return the count. Implement an O(n^
2) solution using expand-around-center, explaining how you handle even-length centers and repeated characters. Then outline how a linear-time approach would work conceptually. Analyze time and space complexity, and discuss edge cases (empty string, single-character string, all identical characters).
Quick Answer: This question evaluates proficiency in string algorithms, algorithmic design, and complexity analysis by targeting palindromic substring counting, string manipulation, and conceptual linear-time techniques.
Given a lowercase ASCII string `s`, count and return the number of substrings of `s` that are palindromes.
Each single character is a palindrome, and substrings at different start/end indices are counted separately even if they are equal as strings (e.g. the two `"a"` substrings in `"aa"` are two distinct palindromic substrings, plus `"aa"` itself, for a total of 3).
Implement the classic O(n^2) **expand-around-center** approach: for every possible center, expand outward while the left and right characters match, counting one palindrome per successful expansion. There are `2n - 1` centers — `n` odd-length centers (a single character) and `n - 1` even-length centers (the gap between two adjacent characters), which is how repeated characters and even-length palindromes are handled.
Return the total count. For the empty string, return 0.
Constraints
- 0 <= len(s) <= 1000
- s consists of lowercase ASCII letters ('a'-'z') only
- Return value fits in a 32-bit signed integer for the given length bound
Examples
Input: ("abc",)
Expected Output: 3
Explanation: Only the three single characters 'a', 'b', 'c' are palindromes; no longer substring is a palindrome.
Input: ("aaa",)
Expected Output: 6
Explanation: Singles: 'a','a','a' (3). Length-2: 'aa','aa' (2). Length-3: 'aaa' (1). Total 6 — every substring is a palindrome.
Hints
- Every palindrome has a center. For a string of length n there are 2n-1 possible centers: n centers on a single character (odd-length palindromes) and n-1 centers between two adjacent characters (even-length palindromes).
- For each center, set two pointers and expand outward while the characters match and you stay in bounds. Each successful expansion (including the initial match) corresponds to exactly one palindromic substring, so increment the count each time.
- To enumerate both center types with one loop, iterate an index c from 0 to 2n-2: let left = c // 2 and right = left + (c % 2). When c is even, left == right (odd-length); when c is odd, right == left + 1 (even-length).
- A linear-time approach (Manacher's algorithm) transforms the string by inserting separators so every palindrome becomes odd-length, then reuses previously computed palindrome radii via a mirror around the current rightmost palindrome to avoid redundant expansions, giving O(n).