Python: Finding Longest Palindrome in String

1. Introduction

A palindrome is a word, number, phrase, or sequence of characters that reads the same forward and backward. Examples include "madam" or "aba". In this post, we will implement and understand an algorithm to find the longest palindrome substring within a given string.

2. Program Overview

1. Define a function to expand around the center and check for a palindrome.

2. Iterate through each character of the string and consider it as a center to expand and find palindromes.

3. Store and update the longest palindrome substring.

4. Return the longest palindrome substring.

3. Code Program

def longest_palindrome(s: str) -> str:
    """Find the longest palindrome substring in s."""
    if not s:
        return ""

    start = 0
    end = 0
    for i in range(len(s)):
        len1 = expand_around_center(s, i, i)
        len2 = expand_around_center(s, i, i + 1)
        max_len = max(len1, len2)
        if max_len > (end - start):
            start = i - (max_len - 1) // 2
            end = i + max_len // 2

    return s[start:end+1]

def expand_around_center(s: str, left: int, right: int) -> int:
    """Helper function to expand around the center and return length."""
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1

# Test
input_str = "babad"
print(f"The longest palindrome substring of {input_str} is: {longest_palindrome(input_str)}")

Output:

The longest palindrome substring of babad is: bab

(Note: The string "babad" also has another palindrome "aba", but the function returns the first longest palindrome it finds.)

4. Step By Step Explanation

1. We start with a helper function expand_around_center that takes a string and two indices as arguments. It tries to expand outwards from the center and returns the length of the palindrome.

2. In the main function longest_palindrome, for each character in the string, we treat it as the center of a possible palindrome. We also account for even length palindromes by considering two adjacent characters as the center.

3. We use the helper function to expand from the center and check for palindromes, storing the start and end indices of the longest palindrome found.

4. Finally, we extract and return the longest palindrome substring using slicing.

Using this approach, we efficiently check for palindrome substrings in the string and return the longest one found.