← SAP questions

Count palindromic substrings

Filed under SAP · Also reported at Accolite, Agoda, Amazon, BNY Mellon, Morgan Stanley

Free read 1 of 3

Iterate through each character and each gap between characters as potential centers of a palindrome.

The question

Given a string, find the count of all unique palindromic substrings.

Constraints

  • String length <= 1000
  • Characters are lowercase English letters
  • Time complexity should be O(n^2)

Examples

Input
aba
Output
2
Why
The palindromic substrings are 'a', 'b', 'aba'. Unique ones are 'a', 'b', 'aba'. Wait, the set is {'a', 'b', 'aba'}, count is 3.

Approach

  1. Iterate through each character and each gap between characters as potential centers of a palindrome.

Solution

O(n^2) time, O(n^2) space

Python
def count_unique_palindromes(s):
    res = set()
    for i in range(len(s)):
        for l, r in [(i, i), (i, i + 1)]:
            while l >= 0 and r < len(s) and s[l] == s[r]:
                res.add(s[l:r+1])
                l -= 1; r += 1
    return len(res)

Tips

  • What they are testing: Test with empty strings and strings with all identical characters.
  • Common mistake: Counting duplicate palindromes instead of using a set to track unique ones.

Related SAP questions

Collected from public candidate posts and coding forums. Updated Nov 2026.