Find all distinct palindromic sub-strings for a given string

I was solving a question where I had to find all possible unique palindromes of size greater than 1 for a string.

I was able to come up with the solution shown below. If I am not mistaken it is an \$O(n^2)\$ solution. I'd like feedback on improving the code and if my understanding of its time complexity is correct.

def check_palin(word):
    for i in xrange(len(word)/2):
        if word[i] != word[-1*(i+1)]:
            return False
    return True

def all_palindromes(string):

    left,right=0,len(string)
    j=right
    results=[]

    while left < right-1:
        temp = string[left:j] #Time complexity O(k)
        j-=1

        if check_palin(temp):
            results.append(temp)

        if j<left+2:
            left+=1
            j=right

    return list(set(results))

print all_palindromes("racecarenterelephantmalayalam")

Output:

['aceca', 'layal', 'cec', 'alayala', 'racecar', 'ele', 'ere', 'aya', 'malayalam', 'ala']

Time complexity

Yes, your solution has a O(n^2) time complexity. As the output is n^2 where the input is n, achieving a better time complexity is impossible.

Look at the following code + output:

for i in range(1, 51):
    string = "a" * i
    permutations = list(palindrome_substrings("a"*i))
    print(len(string), len(permutations), len(permutations) /  float(len(string)))

(1, 1, 1.0)
(2, 3, 1.5)
(3, 6, 2.0)
(4, 10, 2.5)
(5, 15, 3.0)
(6, 21, 3.5)
(7, 28, 4.0)
(8, 36, 4.5)
(9, 45, 5.0)
(10, 55, 5.5)
(11, 66, 6.0)
(12, 78, 6.5)
(13, 91, 7.0)
(14, 105, 7.5)
(15, 120, 8.0)
(16, 136, 8.5)
(17, 153, 9.0)
(18, 171, 9.5)
(19, 190, 10.0)
(20, 210, 10.5)
(21, 231, 11.0)
(22, 253, 11.5)
(23, 276, 12.0)
(24, 300, 12.5)
(25, 325, 13.0)
(26, 351, 13.5)
(27, 378, 14.0)
(28, 406, 14.5)
(29, 435, 15.0)
(30, 465, 15.5)
(31, 496, 16.0)
(32, 528, 16.5)
(33, 561, 17.0)
(34, 595, 17.5)
(35, 630, 18.0)
(36, 666, 18.5)
(37, 703, 19.0)
(38, 741, 19.5)
(39, 780, 20.0)
(40, 820, 20.5)
(41, 861, 21.0)
(42, 903, 21.5)
(43, 946, 22.0)
(44, 990, 22.5)
(45, 1035, 23.0)
(46, 1081, 23.5)
(47, 1128, 24.0)
(48, 1176, 24.5)
(49, 1225, 25.0)
(50, 1275, 25.5)

As you can see, not only the output size grows with the input, the ratio between output size and input size grows too. This means that the time complexity is quadratic.

Generators and all

As far as the code is concerned, it is not Pythonic, it looks like C as it does not make use of generator expressions and built-ins like any or all.

def is_palindrome(word):
    return all(word[i] == word[-1*(i+1)] for i in xrange(len(word)//2))

I kept your way of looping and multiplying by -1, but now the code reads at a higher level: all the i-th chars must equal the (-1 * (i+1)) - th chars. And the efficiency is the same as all short-circuites (aborts the computation as soon as it finds a counterexample.)

Separation of concerns

Getting the substrings of a string is interesting in its own right.Why am I forced to get only the palindrome ones? Make substrings a separate function.

Going one level deeper

You can actually nest the loops in the generator expression, getting the substrings of a string may be written as:

def substrings(string):
    return (string[i:j+1] for i in range(len(string)) for j in range(i, len(string)))

Or in a more imperative-looking (but equivalent) manner:

def substrings(string):
    for i in range(len(string)):
        for j in range(i, len(string))):
            yield string[i:j+1]

The final function

And getting the palindrome substrings is now very easy:

def palindrome_substrings(string):
    return (i for i in substrings(string) if is_palindrome(i))

Side note about names

Use long descriptive names, over cryptic abbreviations:

-
check_palin -> check_palindrome or following the is_ convention (boolean-returning functions should have a name starting with is_) is_palindrome

-
all_palindromes: What does all stand for? It stands for substrings so just write it like that: -> palindrome_substrings

Bug fix

a is a palindrome, in general all single char strings are palindromes, so your code not returning them means it has a bug. My code rightly returns single char palindromes.

StackExchange Code Review Q#110079, answer score: 7