5
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ @BCdotWEB Yes those are very useful :) Here is the list \$\endgroup\$ – Aryan Parekh Nov 17 at 3:30
  • 1
    \$\begingroup\$ Why can't you give us the link to the problem? \$\endgroup\$ – superb rain Nov 17 at 13:32
  • 1
    \$\begingroup\$ @superbrain I found the same problem on LeetCode. \$\endgroup\$ – Marc Nov 17 at 14:33
  • \$\begingroup\$ @Marc That might have different input size limits, time/memory limits, and test cases, though. \$\endgroup\$ – superb rain Nov 17 at 15:08
  • \$\begingroup\$ @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. \$\endgroup\$ – superb rain Nov 17 at 15:25
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ How did you measure to get "2/3"? I'd expect a better improvement from switching from O(n^3) to O(n^2). \$\endgroup\$ – superb rain Nov 17 at 13:30
  • \$\begingroup\$ I just used the %timeit magic in a Jupyter notebook. But I only ran it on fairly short strings (upto 15-20 chars). \$\endgroup\$ – RootTwo Nov 17 at 15:58
2
\$\begingroup\$

Welcome to Code Review. @RootTwo already provided a more efficient approach. I'll add a couple of suggestions about your code:

  • 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
    
| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.)

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.