# How to Find All Palindromes in a Python String?

## 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

# ['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Β³)`.

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