Count palindromic substrings
Filed under SAP · Also reported at Accolite, Agoda, Amazon, BNY Mellon, Morgan Stanley
Free read 1 of 3Iterate 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
Iterate through each character and each gap between characters as potential centers of a palindrome.
Expand outwards while characters match to find all palindromes.
Add every found palindrome to a set to ensure uniqueness.
Return the size of the set.
Solution
O(n^2) time, O(n^2) space
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.