## Coding Challenge

š¬ **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 `'madam'`

, `'anna'`

, or `'101'`

.

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

You can easily check if a string is a palindrome by using the slicing expression `word == word[::-1]`

that evaluates to `True`

if the word is the same forward and backward, i.e., it is a 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']

## Runtime Complexity

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.