Longest Palindromic Substring - Python Solution

1. Introduction

The "Longest Palindromic Substring" problem is a classic challenge in string processing and dynamic programming. It involves finding the longest contiguous sequence of characters in a string that reads the same forwards and backwards. This problem is a great exercise for understanding string manipulation and algorithm optimization techniques.


Given a string s, the task is to return the longest palindromic substring in s. A palindrome is a string that reads the same forward and backward.

2. Solution Steps

1. Initialize variables to store the start and length of the longest palindrome found.

2. Iterate through each character in the string, treating it as the center of a potential palindrome.

3. Expand around the center to find the longest palindrome for both even and odd length palindromes.

4. Update the start and length variables if a longer palindrome is found.

5. Return the longest palindromic substring using the start and length variables.

3. Code Program

def longestPalindrome(s):
    if not s or len(s) < 1:
        return ""

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

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

    return s[start:end + 1]

# Example Usage


"bab" or "aba"


1. Center Expansion: The function expandAroundCenter checks for the longest palindrome around a given center.

2. Even and Odd Palindromes: The algorithm tests for both even and odd length palindromes by expanding around one or two center points.

3. Maximum Length: The length of the longest palindrome found at each center is compared to the current maximum.

4. Updating Start and End: If a longer palindrome is found, the start and end indices are updated accordingly.

5. Result: The function returns the substring of s that represents the longest palindromic substring.