3

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
  • 47,440
  • 4
  • 68
  • 97
Clock Slave
  • 7,627
  • 15
  • 68
  • 109
  • 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
  • 5
    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).

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
  • 72,016
  • 6
  • 67
  • 89