Longest Palindromic Substring in Python

This Python program finds the longest palindromic substring within a given string. A palindrome is a string that reads the same forwards and backwards, like “racecar” or “level”.

Program Explanation

The program uses the “expand around center” approach to identify the longest palindromic substring. The idea is to consider each character and each pair of characters in the string as potential centers of palindromes and expand outwards as long as the characters on both sides are equal. This method runs in O(n^2) time complexity, where n is the length of the string.

Python Code

def longest_palindromic_substring(s):
    """
    Function to find the longest palindromic substring in a given string.
    
    Args:
        s (str): The input string.
    
    Returns:
        str: The longest palindromic substring.
    """
    
    if not s:
        return ""
    
    def expand_around_center(left, right):
        """
        Expand around the center and return the longest palindromic substring
        for the given left and right indices.
        
        Args:
            left (int): The starting index of the left part of the center.
            right (int): The starting index of the right part of the center.
        
        Returns:
            str: The longest palindromic substring found by expanding around the center.
        """
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]
    
    longest = ""
    
    for i in range(len(s)):
        # Odd length palindromes
        palindrome1 = expand_around_center(i, i)
        # Even length palindromes
        palindrome2 = expand_around_center(i, i + 1)
        
        # Update longest palindrome if a longer one is found
        if len(palindrome1) > len(longest):
            longest = palindrome1
        if len(palindrome2) > len(longest):
            longest = palindrome2
    
    return longest

# Example usage
input_string = "babad"
print("Longest Palindromic Substring:", longest_palindromic_substring(input_string))
    

Code Description

• longest_palindromic_substring(s): This function is the main function to find the longest palindromic substring. It initializes the longest palindrome to an empty string.
• expand_around_center(left, right): This helper function expands around the center to find the longest palindromic substring starting from the given left and right indices.
• The program iterates through each character in the string, considering both single characters (for odd length palindromes) and pairs of characters (for even length palindromes) as potential centers.
• It updates the longest palindrome found and returns it as the result.