💬 Challenge: Given a string. How to find all palindromes in the string?
For comprehensibility, allow me to quickly add a definition of the term palindrome:
💡 Definition: A palindrome is a sequence of characters that reads the same backward as forward such as
This article wants to give you a quick and easy solution in Python. First, we’ll solve the easier but important problem of checking if a substring is a palindrome in the first place:
How to Check If String is Palindrome
👉 Recommended Tutorial: Python Palindromes One-Liner
Next, we’ll explore how to find all substrings in a Python string that are also palindromes. You can find our palindrome checker in the code solution (highlighted):
Find All Substrings That Are Palindrome
The brute-force approach to finding all palindromes in a string is to iterate over all substrings in a nested
for loop. Then check each substring if it is a palindrome using
word == word[::-1]. Keep track of the found palindromes using the
list.append() method. Return the final list after traversing all substrings.
Here’s the full solution:
def find_palindromes(s): palindromes =  n = len(s) for i in range(n): for j in range(i+1,n+1): word = s[i:j] if word == word[::-1]: palindromes.append(word) return palindromes print(find_palindromes('locoannamadam')) # ['l', 'o', 'oco', 'c', 'o', 'a', 'anna', # 'n', 'nn', 'n', 'a', 'ama', 'm', 'madam', # 'a', 'ada', 'd', 'a', 'm'] print(find_palindromes('anna')) # ['a', 'anna', 'n', 'nn', 'n', 'a'] print(find_palindromes('abc')) # ['a', 'b', 'c']
This has cubic runtime complexity, i.e., for a string with length
n, we need to check
O(n*n) different words. Each word may have up to
n characters, thus the palindrome check itself is
O(n). Together, this yields runtime complexity of
O(n*n*n) = O(n³).
Quadratic Runtime Solutions
Is this the best we can do? No! There’s also an O(n²) time solution!
Here’s a quadratic-runtime solution to find all palindromes in a given string that ignores the trivial one-character palindromes (significantly modified from source):
def find_palindromes(s, j, k): ''' Finds palindromes in substring between indices j and k''' palindromes =  while j >= 0 and k < len(s): if s[j] != s[k]: break palindromes.append(s[j: k + 1]) j -= 1 k += 1 return palindromes def find_all(s): '''Finds all palindromes (non-trivial) in string s''' palindromes =  for i in range(0, len(s)): palindromes.extend(find_palindromes(s, i-1, i+1)) palindromes.extend(find_palindromes(s, i, i+1)) return palindromes print(find_all('locoannamadam')) # ['oco', 'nn', 'anna', 'ama', 'ada', 'madam'] print(find_all('anna')) # ['nn', 'anna'] print(find_all('abc')) # 
Feel free to join our community of ambitious learners like you (we have cheat sheets too): ❤️
While working as a researcher in distributed systems, Dr. Christian Mayer found his love for teaching computer science students.
To help students reach higher levels of Python success, he founded the programming education website Finxter.com that has taught exponential skills to millions of coders worldwide. He’s the author of the best-selling programming books Python One-Liners (NoStarch 2020), The Art of Clean Code (NoStarch 2022), and The Book of Dash (NoStarch 2022). Chris also coauthored the Coffee Break Python series of self-published books. He’s a computer science enthusiast, freelancer, and owner of one of the top 10 largest Python blogs worldwide.
His passions are writing, reading, and coding. But his greatest passion is to serve aspiring coders through Finxter and help them to boost their skills. You can join his free email academy here.