Katkat
Back

Count Palindromic Substrings

Goldman SachsData Scientist · Online Assessment
EasyData ScientistOnline AssessmentCoding & Algorithms

Last updated

This question tests your ability to identify palindromes within a string using expansion around centers or dynamic programming.

Count Palindromic Substrings

Given a string s, return the total number of contiguous palindromic substrings in s.

A string is a palindrome when it reads the same backward as forward. Substrings that have identical characters but appear at different starting or ending positions are counted separately.

Function Signature

def count_palindromic_substrings(s: str) -> int:
    pass

Input

  • s: A string consisting of lowercase English letters.

Output

  • An integer representing the total count of palindromic substrings.

Constraints

  • 1 <= len(s) <= 1000
  • s consists solely of lowercase English letters ('a' - 'z').

Examples

Example 1:

Input: s = "abc"
Output: 3
Explanation: Three palindromic substrings: "a", "b", "c".

Example 2:

Input: s = "aaa"
Output: 6
Explanation: Six palindromic substrings: "a", "a", "a", "aa", "aa", "aaa".

Edge Cases

  • Single character string (len(s) == 1): always returns 1.
  • String where all characters are identical: maximum number of palindromes, equal to n * (n + 1) // 2.
  • String with no adjacent matching characters: only single characters form palindromes.

Hints

Hint 1

Notice that every palindrome has a center, which can be a single character (odd length) or between two characters (even length).

Hint 2

There are 2 * n - 1 possible centers in a string of length n; try expanding outward from each center while the characters match.

Hint 3

Expanding outward stops as soon as a mismatch occurs, allowing you to count valid palindromes in O(n^2) time and O(1) extra space.

Follow-up questions

  • How can you achieve O(n) time complexity using Manacher's algorithm?
  • How would you modify your algorithm to return the longest palindromic substring rather than the count?
  • How would you handle a streaming input where characters are appended one at a time?