How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

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.

Input: ("",)

Expected Output: 0

Explanation: Empty string edge case: there are no substrings, so the count is 0.

Input: ("a",)

Expected Output: 1

Explanation: Single-character edge case: the one character is itself a palindrome.

Input: ("abba",)

Expected Output: 6

Explanation: Singles: 4. Even-length center between the two 'b's yields 'bb' and expands to 'abba' (2). Total 6 — exercises even-length centers.

Input: ("aabaa",)

Expected Output: 9

Explanation: Singles: 5. 'aa' (indices 0-1), 'aa' (indices 3-4), 'aba' (1-3), 'aabaa' (0-4) — 4 more. Total 9.

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).

Quick Overview

This question evaluates proficiency in string algorithms, algorithmic design, and complexity analysis by targeting palindromic substring counting, string manipulation, and conceptual linear-time techniques.