Longest Palindromic Substring — Expand Around Center (Clean Intuition)— Neetcode 150

Link : *https://leetcode.com/problems/longest-palindromic-substring/description/*

Difficulty: Medium

Topics: Strings, DP, Recursion, Backtracking

Pattern: Expand Around the Corner

Key Insight:

This problem can be solved using Dynamic Programming, but the expand around center approach is simpler and more intuitive once the idea is clear.

Create a helper function expand(left, right) that takes two indices representing the current center of a potential palindrome.

While left >= 0 and right < n and s[left] == s[right], keep expanding outward:

• Decrease left by 1
• Increase right by 1
• This expansion checks whether the substring continues to remain a palindrome.

Once the condition fails, return the substring from left + 1 to right, which represents the longest palindrome found for that center.

In the main loop, run the expand function for every index i:

• (i, i) → checks for odd-length palindromes
• (i, i + 1) → checks for even-length palindromes
• Compare the returned substrings and keep updating the longest palindrome found so far.

Time and Space Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        def expand(left, right):
            while left>=0 and right<n and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1:right]
        longest = ''
        for i in range(n):

            # For odd there will be a middle element so same index will work
            p1 = expand(i, i)

            # For even length there will be two numbers in the middle
            p2 = expand(i, i+1)
            longer = p1 if len(p1)>len(p2) else p2
            longest = longer if len(longer) > len(longest) else longest
        return longest

if __name__ == "__main__":
    sol = Solution()
    assert sol.longestPalindrome("babad") == "bab"
    assert sol.longestPalindrome("cbbd") == "bb"
    print("✅ All tests passed!")