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
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&gt;=0 and k&lt;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&gt;=0 and k&lt;len(s) and s[j] == s[k]:
            count += 1
            j -= 1
            k += 1

    return count