Finding the longest palindromic substring

Question

I have the following code that works correctly. I am wondering if there is a simpler way to go about implementing my solution and/or if there is anything that looks non-standard in my code. If anyone wants to offer criticism I'm all ears.

### Question 2 main function and helper functions.
"""Given a string a, find the longest palindromic substring contained in a.
Your function definition should look like question2(a), and return a string."""
# Gives substrings of s in decending order.
def substrings(s):

    # Declare local variable for the length of s.
    l = len(s)

    # Here I chose range over xrange for python version compatibility.
    for end in range(l, 0, -1):
        for i in range(l-end+1):
            yield s[i: i+end]

# Define palindrome.
def palindrome(s):
    return s == s[::-1]

# Main function.
def Question2(a):
    for l in substrings(a):
        if palindrome(l):
            return l

# Simple test case.
print Question2("stresseddesserts")
# stresseddesserts

Answer 1

In terms of efficiency, I like the code.

I'd just fix a few stylistic issues:

• Naming: l, a, s don't say anything about what the variable means. Also, you named your function palindrome, but that's returning a boolean, so I'd name it is_palindrome. The i in the substring function is a bit puzzling to me: you have a variable named end, why not call the other one start?

• As @kyrill mentioned, you should probably change comments above the functions to docstrings.

• The comment Declare local variable for the length of s. is useless.

• I'd instead add another comment explaining why it works. If you have a function simply called substrings I expect it to return the substrings. This code only works because it returns the substrings starting from the longest to the shortest. I'd at least change the comment descending order (which may mean for example lexicographical order or alphabetical order) to from longest to shortest. Better be explicit.

• I know, it's a bit long, but since you're using a generator, I'd rename the function substrings to get_next_substring.

• As @zondo mentioned Question2 is not a PEP8 compliant name, but I'm not sure if the automatic grader will need it to be called like that.

Answer 2

I saw your substrings function and expected to tell you to use yield instead of creating a list, but you already do. I also like your comment on why you use range. If you want to be completely compatible with Python 3, though, you'll need to use parentheses for print:

print(Question2("stresseddesserts"))

The only other thing I'll mention is that Question2 does not follow official Python naming guidelines as defined in PEP 8. According to that document, function names should use snake_case. Your assignment also uses lowercase, so I'm a little surprised you changed it especially since your other functions are lowercase.

All in all, the program is concise, efficient, and organized. Well done.

Answer 3

1. BUG: Your main loop for l in substrings(a): ... will return the first palindrome it finds inside a (stepping the indices back from the end), not just the longest one. If there are multiple longest palindromes it won't return them all, only the first it finds. Your code is overly tailored to this one example. Use other examples to tickle it, e.g. "zaba effeffe xyx". Your main function should yield all candidates of longest length (or else keep a list), only then can it finish.
2. Obfuscated loop variables:
   • l is totally unnecessary, get rid of it
   • The variable you call end isn't an end. It's a length or span: s[i: i+end] instead of s[i:end]. And look at the acrobatics you pull with for i in range(l-end+1): ... that's really just a severely obfuscated way of writing nested loops with indices:

    for i in range(l):
      for j in range(l, i, -1):
        # Now reference s[i:j]

3. But that iterator function substrings() is just a verbose way of doing what a generator expression or list comprehension could do in one line:

s[i:j] for i in range(l) for j in range(l, i, -1)

4. INEFFICIENCY: your loop only needs to run the j/end index as far back as i, not 0. Once j < i, then s[i:j] will be empty-string, that's ~2x wasted iterations.