2

I am trying to check if a string contains any substring of length > 1 which is a palindrome. (Note that this is not the same as checking if the whole string is a palindrome.) I was able to write a function that finds even- or odd-length palindrome substrings; I have optimized it to the best of my ability, but my code exceeds the time limit for a few test cases.

How can I improve the algorithm to make it faster?

def findPalindrome(s):
    ans = ""
    for i in range(len(s)):
        for k in range(2):
            temp = str_parser(s, i, i + k)
            if len(temp) > len(ans) and len(temp) > 1:
                return 1
    return 0


def str_parser(s, l, r):
    while l >= 0 and r < len(s):
        if s[r] == s[l] and len(s[l:r+1]) > 1:
            return s[l:r+1]
        else:
            l -= 1
            r += 1
    return ''

The findPalindrome function returns 1 if the input string contains a palindrome, otherwise it returns 0.

kaya3
  • 41,043
  • 4
  • 50
  • 79
Clock Slave
  • 6,997
  • 9
  • 61
  • 98
  • 1
    A simple hint: Start from both the start and the end and compare each letter until you reach the middle. – Aethernite Aug 09 '21 at 07:59
  • @Aethernite this is checking for a substring palindrome, not just of the word itself – Ani M Aug 09 '21 at 08:00
  • 4
    Check on Manacher's Algorithm for finding all sub-palindromes in O(N). You can certainly modify the algorithm to return true on the first found palindrome. – Aethernite Aug 09 '21 at 08:10

2 Answers2

7

As you are just asking for palindromes of length greater than one, it suffices to look for patterns aa or aba. This is done in a single, linear pass, taking N-1+N-2 comparisons at worst (and 1 comparison at best).

Yves Daoust
  • 53,540
  • 8
  • 41
  • 94
5

As has been pointed out, all you have to do is check if there are palindromes of length 2 or 3:

def findPalindrome(s):
    return any(x==y for x,y in zip(s, s[1:])) or any(x==y for x,y in zip(s, s[2:]))

Or more concisely:

return any(c in s[i+1:i+3] for i, c in enumerate(s))
user2390182
  • 67,685
  • 6
  • 55
  • 77