Hello, I am an Engineering Manager at Facebook with 13+ years in Ad Technology, Natural Language Processing and Data mining. (Learn More)
by Pravin Paratey

Palindromic sub-sequences in python

This bit of code returns all palindromic subsequences in the input string. If the line marked #In-efficient is better implemented (I am lazy), the running time is O(n<sup>2</sup>). Can you find a better solution?

#!/usr/bin/env python

def get_palindromes(str):
    """ Return all palindromes in str of minimum size 3 """
    length = len(str) + 1
    
    found = []
    for i in xrange(0, length):
        for j in xrange(i+3, length):
            mid = i + ((j - i) / 2)
            if str[i:mid] == str[mid+1:j][::-1]: # In-efficient
                found.append(str[i:j])
    return found    

if __name__ == '__main__':
    print get_palindromes('efeababaf')