Python Program to Find All Palindrome Substrings

You can find all palindrome substrings in Python by expanding around each character and its neighbor using a function like expand_around_center and collecting substrings where left == right while expanding.

Examples

Inputabba

Output['a', 'b', 'b', 'a', 'bb', 'abba']

Inputabc

Output['a', 'b', 'c']

Inputaaa

Output['a', 'a', 'a', 'aa', 'aa', 'aaa']

How to Think About It

To find all palindrome substrings, think of each character and the gap between characters as a center. From each center, expand outwards while the characters on both sides are the same. Collect all substrings found this way because they are palindromes.

Algorithm

1

Get the input string.

2

For each index in the string, treat it as the center of odd-length palindromes and expand outwards.

3

For each index, also treat the gap between this index and the next as the center of even-length palindromes and expand outwards.

4

Collect all substrings found during expansions that are palindromes.

5

Return the list of all palindrome substrings.

Code

python

def find_palindromes(s):
    result = []
    def expand_around_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            result.append(s[left:right+1])
            left -= 1
            right += 1
    for i in range(len(s)):
        expand_around_center(i, i)       # odd length
        expand_around_center(i, i + 1)   # even length
    return result

input_str = "abba"
print(find_palindromes(input_str))

Output

['a', 'b', 'b', 'a', 'bb', 'abba']

Dry Run

Let's trace 'abba' through the code

1

Start with i=0 (center at 'a')

Expand around center (0,0): substring 'a' is palindrome, add 'a'. Expand stops as next chars differ.

2

Check even center (0,1) between 'a' and 'b'

Characters differ, no palindrome added.

3

i=1 (center at 'b')

Expand around (1,1): 'b' added. Expand around (1,2): 'bb' added, then expand further to 'abba' added.

4

i=2 (center at 'b')

Expand around (2,2): 'b' added. Expand around (2,3): 'ba' no palindrome.

5

i=3 (center at 'a')

Expand around (3,3): 'a' added. Expand around (3,4): out of bounds.

Center	Palindromes Found
(0,0)	a
(0,1)
(1,1)	b
(1,2)	bb, abba
(2,2)	b
(2,3)
(3,3)	a
(3,4)

Why This Works

Step 1: Expand Around Centers

The code checks palindromes by expanding around each character and between characters, because palindromes can be odd or even length.

Step 2: Check Characters Match

While expanding, it compares characters on both sides; if they match, the substring is a palindrome.

Step 3: Collect Palindromes

Each time a palindrome substring is found, it is added to the result list.

Alternative Approaches

Dynamic Programming

python

def find_palindromes_dp(s):
    n = len(s)
    dp = [[False]*n for _ in range(n)]
    result = []
    for length in range(1, n+1):
        for start in range(n-length+1):
            end = start + length - 1
            if s[start] == s[end] and (length <= 2 or dp[start+1][end-1]):
                dp[start][end] = True
                result.append(s[start:end+1])
    return result

print(find_palindromes_dp('abba'))

Uses a table to remember palindrome substrings, good for repeated checks but uses more memory.

Brute Force Check All Substrings

python

def is_palindrome(sub):
    return sub == sub[::-1]

def find_palindromes_brute(s):
    result = []
    for i in range(len(s)):
        for j in range(i, len(s)):
            if is_palindrome(s[i:j+1]):
                result.append(s[i:j+1])
    return result

print(find_palindromes_brute('abba'))

Simple but slow because it checks every substring explicitly.

Complexity: O(n^2) time, O(n^2) space

Time Complexity

The algorithm expands around each character and between characters, each expansion can take up to O(n), repeated for n centers, resulting in O(n^2).

Space Complexity

The result list can hold up to O(n^2) substrings in the worst case, so space is O(n^2).

Which Approach is Fastest?

The expand-around-center method is generally faster and simpler than brute force, and uses less memory than dynamic programming.

Approach	Time	Space	Best For
Expand Around Center	O(n^2)	O(n^2)	Balanced speed and memory
Dynamic Programming	O(n^2)	O(n^2)	Repeated palindrome queries
Brute Force	O(n^3)	O(n^2)	Simple but slow, small inputs