Python: Finding Longest Palindrome in String

📘 Premium Read: Access my best content on Medium member-only articles — deep dives into Java, Spring Boot, Microservices, backend architecture, interview preparation, career advice, and industry-standard best practices.

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (176K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

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.