Count palindrome substrings in a string
MetaSoftware Engineer · Technical Screen
Last updated
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 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).
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.