🟨 Longest Palindromic Substring (#5)

🔗 Problem Link

• LeetCode - Longest Palindromic Substring
• NeetCode - Longest Palindromic Substring

📋 Problem Statement

Given a string s, return the longest palindromic substring in s.

💡 Examples

Example 1

Input: s = "babad"
Output: "bab" (or "aba")

Example 2

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

🔑 Key Insights & Approach

Core Observation: Expand around center for each possible center (n centers for odd, n-1 for even length palindromes).

Why Expand Around Center?

• O(n²) time, O(1) space
• Check all possible centers
• Better than DP's O(n²) space

Pattern: "Expand Around Center" for palindrome problems.

🐍 Solution: Python

Approach: Expand Around Center

Time Complexity: O(n²) | Space Complexity: O(1)

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

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

        start, max_len = 0, 0

        for i in range(len(s)):
            # Odd length palindrome
            len1 = expand_around_center(i, i)
            # Even length palindrome
            len2 = expand_around_center(i, i + 1)

            curr_len = max(len1, len2)
            if curr_len > max_len:
                max_len = curr_len
                start = i - (curr_len - 1) // 2

        return s[start:start + max_len]

🔵 Solution: Golang

Approach: Expand Around Center

Time Complexity: O(n²) | Space Complexity: O(1)

func longestPalindrome(s string) string {
    if len(s) == 0 {
        return ""
    }

    expandAroundCenter := func(left, right int) int {
        for left >= 0 && right < len(s) && s[left] == s[right] {
            left--
            right++
        }
        return right - left - 1
    }

    start, maxLen := 0, 0

    for i := 0; i < len(s); i++ {
        len1 := expandAroundCenter(i, i)
        len2 := expandAroundCenter(i, i+1)

        currLen := len1
        if len2 > currLen {
            currLen = len2
        }

        if currLen > maxLen {
            maxLen = currLen
            start = i - (currLen-1)/2
        }
    }

    return s[start : start+maxLen]
}

📚 References

• NeetCode - Longest Palindromic Substring