# Hackerrank: Count the number of palindromes in a given string

I am solving a problem for Hackerrank where I have to count the number of palindromes in a given string.

I have the following code which counts the number of palindromes accurately but times out for large strings. How do I make the code more time-efficient?

def countPalindromes(s):
num_palindrome = 0

for i in range(len(s)):
for j in range(i + 1, len(s) + 1):
substring = s[i: j]
if len(substring) == 1:
num_palindrome += 1
else:
for idx in range(len(substring)):
if substring[idx] != substring[-idx-1]:
num_palindrome -= 1
break
num_palindrome += 1

return num_palindrome

• @BCdotWEB Yes those are very useful :) Here is the list Nov 17 '20 at 3:30
• Why can't you give us the link to the problem? Nov 17 '20 at 13:32
• @superbrain I found the same problem on LeetCode.
– Marc
Nov 17 '20 at 14:33
• @Marc That might have different input size limits, time/memory limits, and test cases, though. Nov 17 '20 at 15:08
• @Marc Oh and different allowed characters, too. For example if it's only letters, then RootTwo's solution could replace j>=0 and k<len(s) with sentinels, like with s = '[' + s + ']' at the start. That would make it faster, but whether that's possible depends on the allowed input characters. Nov 17 '20 at 15:25

For each position in the string your code checks all substrings that start at that position. For example, for s = 'a2b3bb3443bab' and i = 3, the code checks '3', '3b', '3bb', '3bb3', ..., '3bb3443bab'. That is O(n^2) strings to palindrome check.

Instead, for each position in the string, check for palindomes that are centered on that position. For example, for s = 'a2b3bb3443bab' and i = 3, check the substrings '3', 'b3b', and '2b3bb'. Stop there, because no other string centered on i = 3 can be a palindrome. It also needs to check for palindromes with an even length such as at i = 4, where we check 'bb', '3bb3' and stop at 'b3bb34'. I think it's O(n*p) where p is the average length of a palindrome (which is less than n). It seems to take about 2/3 as long as you code.

def pcount(s):
count = 0

for i in range(len(s)):
# count the odd-length palindromes
# centered at s[i]
j=i
k=i
while j>=0 and k<len(s) and s[j] == s[k]:
count += 1
j -= 1
k += 1

# count the even-length palindromes
# centered at s[i:i+1]
j = i
k = i + 1
while j>=0 and k<len(s) and s[j] == s[k]:
count += 1
j -= 1
k += 1

return count

• How did you measure to get "2/3"? I'd expect a better improvement from switching from O(n^3) to O(n^2). Nov 17 '20 at 13:30
• I just used the %timeit magic in a Jupyter notebook. But I only ran it on fairly short strings (upto 15-20 chars). Nov 17 '20 at 15:58

• Naming: prefer underscores for function names. count_palindromes instead of countPalindromes.
• Checking if a string is palindrome: this part:
if len(substring) == 1:
num_palindrome += 1
else:
for idx in range(len(substring)):
if substring[idx] != substring[-idx-1]:
num_palindrome -= 1
break
num_palindrome += 1

Can be shorten to:
if substring == substring[::-1]:
num_palindrome += 1


Your

            if len(substring) == 1:
num_palindrome += 1
else:


is unnecessary, as the code in the else part can handle single-character substrings as well. Ok, you make that special case faster, but you're making all other cases slower. And there are more of the latter. So this optimization attempt might very well make the solution as a whole slower.

If you do want to avoid the innermost checking for single-character substrings, an easy and faster way is to start j at i + 2 instead of i + 1 (and initialize with num_palindrome = len(s) to make up for it, i.e., "count" the single-character substrings in advance).

A short solution based on RootTwo's:

from os.path import commonprefix

def count_palindromes(s):
return sum(len(commonprefix((s[i::-1], s[k:])))
for i in range(len(s))
for k in (i, i+1))


Demo:

>>> count_palindromes('foo')
4
>>> count_palindromes('mississippi')
20
`

The latter are:

• 11 palindromes of length 1
• 3 palindromes of length 2
• 1 palindrome of length 3
• 3 palindromes of length 4
• 1 palindrome of length 5
• 1 palindrome of length 7

(Pretty nice test case for correctness, I think.)