Fastest way to check if a string contains a palindrome substring

user_2324298 0
Viewed 2824

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.

palindrome substring algorithm python string
2 Answers

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

user_11965490

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))
user_23901820
Related