5. Longest Palindromic Substring | LeetCode Solutions

Problem Description

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

A palindrome is a string that reads the same backward as forward, such as "madam" or "racecar".

Examples:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

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

Solution Approach

There are multiple approaches to solve this problem, including:

Brute force (check all substrings) - O(n³) time complexity
Dynamic programming - O(n²) time and space complexity
Expand around center - O(n²) time and O(1) space complexity
Manacher's algorithm - O(n) time complexity (advanced)

In this solution, I'll implement the "expand around center" approach, which is efficient and intuitive:

For each position in the string, treat it as a potential center of a palindrome
For each center, expand outward and check if characters match
Consider both odd-length palindromes (single character center) and even-length palindromes (two character centers)
Keep track of the longest palindrome found

Time Complexity: O(n²) where n is the length of the string. For each of the n positions, we might expand up to n/2 times.

Space Complexity: O(1) as we only use a constant amount of extra space.

Python Implementation:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
            
        start = end = 0
        
        for i in range(len(s)):
            # Expand around center for odd length palindromes
            len1 = self.expand_around_center(s, i, i)
            # Expand around center for even length palindromes
            len2 = self.expand_around_center(s, i, i + 1)
            # Get the longer palindrome length
            max_len = max(len1, len2)
            
            # Update result indices if we found a longer palindrome
            if max_len > end - start:
                start = i - (max_len - 1) // 2
                end = i + max_len // 2
                
        return s[start:end+1]
    
    def expand_around_center(self, s: str, left: int, right: int) -> int:
        """Expand around center and return palindrome length."""
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        
        # Return palindrome length (right-left-1)
        return right - left - 1