Mahdi Shamlou | Solving LeetCode #5: Longest Palindromic Substring — My Expand-Around-Center Adventure

Source: Dev.to

Hey everyone! Mahdi Shamlou here — keeping the LeetCode classic problems series rolling 🚀

After #4 Median of Two Sorted Arrays, today we’re diving into Problem #5 — Longest Palindromic Substring, another super famous one that shows up in tons of interviews!

Problem Statement

Given a string s, return the longest palindromic substring in s.
A palindrome reads the same forwards and backwards.

Examples

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer (both length 3)

Input: s = "cbbd"
Output: "bb"

Input: s = "a"
Output: "a"

Solution: Expand‑Around‑Center

When I first thought about it, checking every possible substring sounded painful (O(n³) nightmare 😅). Then I realized: palindromes can expand from the center!

The idea is to treat each character (for odd‑length palindromes) and each gap between characters (for even‑length palindromes) as a potential center, then expand outward while the characters match.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        start = 0
        end = 0

        def expand_around_center(left: int, right: int):
            while left >= 0 and right  end - start:
                start, end = l1, r1

            if r2 - l2 > end - start:
                start, end = l2, r2

            # Debug prints (optional)
            # print(f"start : {start} and end : {end}")
            # print("#" * 100)

        return s[start:end + 1]

Complexity Analysis

• Time Complexity: O(n²) – each expansion can take up to O(n) and we have ~2n centers.
• Space Complexity: O(1) – only a few integer variables are used.

References

• Previous post: Mahdi Shamlou | Solving LeetCode #4: Median of Two Sorted Arrays
• Full repository of solutions: GitHub – mahdi0shamlou/LeetCode