Day 73: Python Longest Palindromic Substring – Expand-Around-Center O(n^2) Technique for Max Palindrome (LeetCode #5 Guide)

#challenge #python #algorithms #programming

Welcome to Day 73 of the #80DaysOfChallenges journey! This intermediate challenge solves the longest palindromic substring problem (LeetCode #5), finding the longest contiguous palindrome in a string using the elegant expand-around-center technique in O(n^2) time. It treats every position as a potential odd/even center and expands while characters match, tracking the longest found with start/max_len. If you're mastering string DP alternatives, prepping for interviews with palindrome questions, or analyzing text symmetry, this "Python longest palindrome" script is efficient, intuitive, and easy to extend for counts or all palindromes.

💡 Key Takeaways from Day 73: Longest Palindrome Function

This task features a function that checks odd and even centers at each index, expanding while symmetric, updating best on longer finds. It's an expand pattern: center outward while match. We'll detail: function with start/max_len trackers, loop for odd/even expansions, and main with input and length print.

1. Function Design: Empty Check and Trackers

The longest_palindrome function takes s, returns substring:

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

    start = 0               # start index of best palindrome
    max_len = 1             # length of best palindrome

Empty returns "", init start=0 len=1 (single char always palindrome).

2. Loop Processing: Odd and Even Center Expansions

Core for each i:

    for i in range(len(s)):
        # check odd-length palindromes (single center)
        left = right = i
        while left >= 0 and right < len(s) and s[left] == s[right]:
            curr_len = right - left + 1
            if curr_len > max_len:
                start = left
                max_len = curr_len
            left -= 1
            right += 1

        # check even-length palindromes (double center)
        left = i
        right = i + 1
        while left >= 0 and right < len(s) and s[left] == s[right]:
            curr_len = right - left + 1
            if curr_len > max_len:
                start = left
                max_len = curr_len
            left -= 1
            right += 1

    return s[start:start + max_len]

Odd: center i, expand left/right. Even: center i/i+1. While bounds and match, compute len, update if longer. For "babad": finds "bab" or "aba" len 3.

3. Main Interactive: Input and Result

Script prompts, calls, prints:

text = input("Enter a string: ").strip()
result = longest_palindrome(text)

print(f"Longest palindromic substring: {result}")
print(f"Length: {len(result)}")