Algorithm For Longest Palindrome

I made an brute force algorithm to find the longest palindrome within the string. This palindrome is a substring of the input. Below is the code.


def generate_substrings(string):
"""
avg time: O(len(string) * len(string))
avg space: O(1)

amortized time: O(len(string) * len(string))
amortized space: O(1)
"""
col = 0
for row in range(len(string)):
col = row + 1
while col < len(string) + 1:
yield string[row:col]
col = col + 1

def test_generate_substrings():
assert list(generate_substrings('')) == []
assert list(generate_substrings('a')) == ['a']
assert list(generate_substrings('ab')) == ['a', 'ab', 'b']

def is_palindrome(string):
"""
avg time: O(len(string))
avg space: O(len(string))

amortized time: O(len(string))
amortized space: O(len(string))
"""
return string[::-1] == string

def test_is_palindrome():
assert is_palindrome('') == True
assert is_palindrome('ab') == False
assert is_palindrome('bb') == True
assert is_palindrome('abc') == False
assert is_palindrome('ddd') == True

def find_palindrome(string):
"""
avg time: O(len(string) * len(string))
avg space: O(len(string))

amortized time: O(len(string) * len(string))
amortized space: O(len(string))
"""
vec = []

for string in generate_substrings(string):
if is_palindrome(string):
vec.append(string)

for string in vec:

def test_find_palindrome():
assert find_palindrome('ab') == 'b'
assert find_palindrome('aa') == 'aa'

def main():
"""
entry point for test code
"""
test_generate_substrings()
test_is_palindrome()
test_find_palindrome()

if __name__ == '__main__':
main()

$$$$

• What's the point of the time estimates in the doc string? Usually we use these to describe functionality – nluigi Feb 21 at 18:06
• And what's "avg" time and space? How does it differ from the amortized values? – Toby Speight Feb 23 at 14:53
• @TobySpeight Average complexity is the probability distribution with the assumption that any sized input is equally likely to happen. Where amortized is the average where we know the history of the function and can then infer the complexity average. For example appending to an ArrayList (Python's list) is amortized $O(1)$ because when the internal array changes we know we've had $n$ $O(1)$ operations before the $1$ $O(n)$ one so $\frac{nO(1) + O(n)}{n + 1} = O(1)$. I'd guess an ArrayList's append has something like $O(\log(n))$ avg complexity. – Peilonrayz Feb 23 at 16:56

It's good to see code that comes with tests - well done!

I would add some more tests in places. Specifically, we ought to test is_palindrome() with a single-letter input, as that's something that could easily get broken, and find_palindrome() needs testing with some strings where the longest palindrome is at beginning, middle or end.

I'm concerned at

assert find_palindrome('ab') == 'b'


There's nothing in the problem statement that says we couldn't return 'a' instead, so this is actually over-testing the code. There's something similar going in in test_generate_substrings() where we require a specific order (we'd be better testing the result converted to set rather than list, to make the test more reasonable).

In terms of the algorithm, I see an obvious candidate for improvement:

for string in generate_substrings(string):
if is_palindrome(string):
vec.append(string)

for string in vec:


We store all of the palindromes in vec, even though we only want the longest one. So we don't really need vec:

for string in generate_substrings(string):
if is_palindrome(string) and len(answer) <= len(string):

We could do even better if we arrange for generate_substrings() to return all the substrings longest first. Then we wouldn't need to generate or use all the shorter substrings:
for string in generate_substrings_longest_first(string):
`