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

#python #leetcode #programming #algorithms

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"

My solution — the expand-around-center way (this clicked for me!) When I first thought about it, checking every possible substring sounded painful (O(n³) nightmare 😅). Then I imagined and then I realized: palindromes can expand from the center!
Become a member

So I wrote this version — check around each character (for odd-length palindromes) and between each pair (for even-length):

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

        start = 0
        end = 0

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

        for i in range(len(s)):
            # Case 1: Odd length palindrome (center is single char)
            # Example: "aba" → center at 'b'
            l1, r1 = expand_around_center_v2(i, i)

            # Case 2: Even length palindrome (center between two chars)
            # Example: "bb" → center between the two 'b's
            l2, r2 = expand_around_center_v2(i, i + 1)

            if r1 - l1 > end - start:
                start, end = l1, r1

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

            print(f"start : {start} and end : {end}")   # I kept these to watch it grow 😂
            print("#" * 100)

        return s[start:end + 1]

Time Complexity: O(n²)
Space Complexity: O(1) → Perfect!

It feels so elegant — we expand outward as long as characters match, and we do it for every possible center. Time complexity is O(n²) because each expansion can take up to O(n), and we have ~2n centers — but in practice it runs really fast! And also no need to generate all possible substrings (which would be O(n³))

My repo (all solutions are here):

GitHub — mahdi0shamlou/LeetCode: Solve LeetCode Problems

What about you? Did the expand-around-center idea click for you right away, or did you start with something crazier like checking every substring? 😅 Any favorite test cases that break naive solutions?

Share in the comments — I read everything! 🚀

And honestly… after seeing “bb” pop out correctly and watching those print statements show the window growing, I just leaned back, laughed, and thought “yes — this actually works and looks clean!” 😂 Here’s me right after submitting and passing: