How to find all palindrome substrings in Python

Key takeaways:

1. Palindromes are words or phrases that can be read the same way from the front and back, such as "anna."

2. Two approaches for finding palindrome substrings are:

   1. Brute force: Simple but inefficient for large inputs, with a time complexity of $O(n^3)$.

   2. Expand from the center: Efficient and intuitive, with a time complexity of $O(n^2)$.

Problem statement

Write a Python function to find all palindromicPalindromes are words or phrases that read the same backward as they do forward. For example, "radar" and "madam" are palindromes, because they are the same whether you read them from left to right or right to left. substrings in a given input string. The function should return the list of unique substrings.

Example:

Input: "ababa"

Output: ['aba', 'ababa', 'bab', 'aba']

Solution

We will go through two approaches for finding all palindrome substrings in Python:

• Brute force

• Expanding from the center

Approach 1: Brute force

The brute force method is the simplest approach to finding palindrome substrings in a given word. It involves checking every possible substring of the word and verifying if it’s a palindrome.

Here is the Python implementation of the brute force approach:

The code above contains two functions:

1. is_palindrome(word): This helper function checks if a given word is a palindrome by comparing it with its reverse.

2. find_palindromes_bruteforce(word): This function takes an input word and finds all palindrome substrings by iterating through all possible substrings and checking if each one is a palindrome using the is_palindrome function. It returns a list of all palindrome substrings found in the word.

Time and space complexity

The is_palindrome function checks if a given string is a palindrome by comparing it with its reverse, which takes $O(n)$, where $n$ is the length of the string.

The find_palindromes_bruteforce function uses nested loops to generate all possible substrings of the input string and checks each substring for being a palindrome using the is_palindrome function. The outer loop runs $n$times, where $n$ is the length of the input string. The inner loop runs $n−i$ times for each iteration of the outer loop. For the palindrome, check for each substring, is_palindrome is called, and it takes $O(n)$as well. Therefore, the overall time complexity of this solution becomes $O(n^3)$.

The space complexity is $O(1)$, as no extra memory is required for the algorithm to run.

Note: While this method is easy to understand, it’s not efficient for larger words, as it takes $O(n^3)$time.

Approach 2: Expand from the center

A more efficient approach involves taking each character in the word as the center of a potential palindrome. From this center, expand outwards in both directions to check for palindromes. This is done separately for odd-length palindromes (single character at the center) and even-length palindromes (two characters at the center). The expansion stops when the characters on either side are no longer the same.

Here is the Python implementation of this approach:

The code above contains two functions:

• find_palindromes(input_string): This helper function uses a while loop to iteratively find palindrome substrings in the input string. The while loop expands the potential palindrome by decrementing the left index (j) and incrementing the right index (k) while checking if the characters at positions j and k are equal. If the loop condition is met, the substring from j to k is a palindrome and added to the palindromes list.

• find_palindromes_expand_from_center(input_string): This function initializes an empty list called palindromes to store the palindromic substrings found in the input_string. It iterates over the indexes of the characters in the input_string taking them as centers of potential palindrome substrings. For each index i, it calls the find_palindromes function twice:

  • Using the current index i as the center, and i - 1 and i + 1 as the initial left and right indexes for expansion (even-length palindromes).

  • Using the current index i as the center, and i and i+1 as initial left and right for expansion (odd-length palindromes).

Time and space complexity

This approach improves upon the brute-force method by reducing unnecessary checks. Instead of iterating through all possible substrings, it considers only potential centers of palindromes. For each center, it expands outward to check if the characters on both sides are the same.

For each character in the string (and each pair of adjacent characters for even-length palindromes), we expand outward to find palindromes. In the worst-case scenario, where all characters are identical (e.g., "aaaaa"), we might need to traverse the entire length of the string for each center. Since there are $n$ possible centers and expanding from each center takes $O(n)$ in the worst case, therefore, the time complexity is $O(n^2)$.

The space complexity is $O(1)$, as no additional memory is used other than storing the output.

Note: This is a significant improvement over the $O(n^3)$ time complexity of the brute-force method.

Conclusion

In this Answer, we explored two approaches to finding all palindrome substrings in Python. The brute force approach involves checking every possible substring, while the expanding approach starts from each letter and expands to the left and right. Both approaches provide different perspectives on solving the problem.