Algorithm For Longest Palindrome

Question

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))
 """
 answer = ''
 vec = [] 
 
 for string in generate_substrings(string):
 if is_palindrome(string):
 vec.append(string)
 
 for string in vec:
 if len(answer) <= len(string):
 answer = string 
 
 return answer 
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()
 
```

• nluigi: What's the point of the time estimates in the doc string? Usually we use these to describe functionality
• Toby Speight: And what's "avg" time and space? How does it differ from the amortized values?
• Peilonrayz: @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.

Answer 1

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:
 if len(answer) <= len(string):
 answer = string

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):
 answer = 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):
 if is_palindrome(string):
 return string