Advanced Palindrome Algorithms in Python

"When the simple is no longer enough, it’s time to look deeper and discover the beauty of the complex."

Detecting palindromes is a classic programming task, but when working with large strings, multiple checks, or substring searches, we need to apply advanced algorithms.

In this guide, we’ll explore different techniques to solve complex palindrome problems in Python, from dynamic programming to efficient search algorithms.

The most common problem is finding the longest palindromic substring within a string.

Basic brute-force solution (O(n³))

def longest_palindromic_substring(s: str) -> str:
    n = len(s)
    max_pal = ""

    for i in range(n):
        for j in range(i, n):
            sub = s[i:j+1]
            if sub == sub[::-1] and len(sub) > len(max_pal):
                max_pal = sub
    return max_pal

print(longest_palindromic_substring("babad"))

Expected output:

"bab"  # or "aba"

2. Expand Around Center (O(n²))

A more efficient approach is to expand from each index as a center, checking for odd and even palindromes.

def expand_center(s: str, left: int, right: int) -> str:
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return s[left+1:right]

def longest_palindromic_substring(s: str) -> str:
    max_pal = ""
    for i in range(len(s)):
        pal1 = expand_center(s, i, i)     # odd palindrome
        pal2 = expand_center(s, i, i+1)   # even palindrome
        max_pal = max([max_pal, pal1, pal2], key=len)
    return max_pal

print(longest_palindromic_substring("cbbd"))

Expected output:

"bb"

3. Dynamic Programming (O(n²))

Dynamic programming helps check all substrings without recalculating, storing results in a boolean table.

def palindrome_dp(s: str) -> str:
    n = len(s)
    dp = [[False]*n for _ in range(n)]
    start, max_len = 0, 1

    for i in range(n):
        dp[i][i] = True  # single character palindrome

    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2 or dp[i+1][j-1]:
                    dp[i][j] = True
                    if length > max_len:
                        start, max_len = i, length

    return s[start:start+max_len]

print(palindrome_dp("forgeeksskeegfor"))

Expected output:

"geeksskeeg"

4. Manacher’s Algorithm (O(n))

Manacher’s algorithm is the most efficient solution, allowing you to find the longest palindromic substring in linear time.

def manacher(s: str) -> str:
    # Transform string to handle odd/even palindromes
    T = "#" + "#".join(s) + "#"
    n = len(T)
    P = [0] * n
    center = right = 0

    for i in range(n):
        mirror = 2*center - i
        if i < right:
            P[i] = min(right - i, P[mirror])

        # expand around the center
        a, b = i + 1 + P[i], i - 1 - P[i]
        while a < n and b >= 0 and T[a] == T[b]:
            P[i] += 1
            a += 1
            b -= 1

        # update center and right boundary
        if i + P[i] > right:
            center, right = i, i + P[i]

    # get the longest palindrome
    max_len, idx = max((n, i) for i, n in enumerate(P))
    start = (idx - max_len) // 2
    return s[start:start+max_len]

print(manacher("abacdfgdcaba"))

Expected output:

"aba"

Common Problems in Advanced Algorithms

  1. Index handling → in algorithms like Manacher’s, index errors are common.
  2. Memory in DP → 2D tables can be heavy for very large strings.
  3. Even and odd substrings → both must always be considered.
  4. Special characters → normalize the string before applying the algorithm.

Advanced Challenges

  • Find all distinct palindromic substrings in a string.
  • Implement a recursive version with memoization.
  • Adapt the algorithms to work with full phrases instead of single words.

Advanced palindrome algorithms in Python allow you to solve more complex problems efficiently. From basic methods like center expansion to sophisticated techniques like Manacher’s algorithm, mastering these strategies opens the door to bigger challenges in competitive programming, string analysis, and optimized algorithms.

You may also be interested in: