Longest Palindromic Substring

Problem

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

Example 1:

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

Example 2:

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

Constraints:

1 <= s.length <= 1000
s consist of only digits and English letters.

Solution

Approach 1: Expand Around Center

The key insight is that every palindrome has a center. We can expand around each possible center and track the longest palindrome found.

Implementation

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 the valid palindrome (left+1 to right-1)
            return left + 1, right - 1

        start, end = 0, 0

        for i in range(len(s)):
            # Odd length palindromes (center is a single character)
            left1, right1 = expand_around_center(i, i)
            # Even length palindromes (center is between two characters)
            left2, right2 = expand_around_center(i, i + 1)

            # Choose the longer palindrome
            if right1 - left1 > end - start:
                start, end = left1, right1
            if right2 - left2 > end - start:
                start, end = left2, right2

        return s[start:end + 1]

Approach 2: Dynamic Programming

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n < 2:
            return s

        dp = [[False] * n for _ in range(n)]
        start, max_len = 0, 1

        # All single characters are palindromes
        for i in range(n):
            dp[i][i] = True

        # Check for two-character palindromes
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                start = i
                max_len = 2

        # Check for palindromes of length 3 or more
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1

                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    start = i
                    max_len = length

        return s[start:start + max_len]

Approach 3: Manacher’s Algorithm (Optimal)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # Transform string to handle even/odd lengths uniformly
        t = '#'.join('^{}$'.format(s))
        n = len(t)
        p = [0] * n  # p[i] = length of palindrome centered at i
        center = right = 0

        for i in range(1, n - 1):
            # Mirror of i
            mirror = 2 * center - i

            if i < right:
                p[i] = min(right - i, p[mirror])

            # Expand around center i
            while t[i + (1 + p[i])] == t[i - (1 + p[i])]:
                p[i] += 1

            # Update center and right boundary
            if i + p[i] > right:
                center, right = i, i + p[i]

        # Find the longest palindrome
        max_len, center_index = max((length, i) for i, length in enumerate(p))
        start = (center_index - max_len) // 2

        return s[start:start + max_len]

Complexity Analysis

Expand Around Center:

Time Complexity: O(n²), where n is the length of string. For each center, we expand up to O(n).
Space Complexity: O(1), only using constant space.

Dynamic Programming:

Time Complexity: O(n²), filling n² DP table.
Space Complexity: O(n²) for the DP table.

Manacher’s Algorithm:

Time Complexity: O(n), linear time.
Space Complexity: O(n) for the transformed string and p array.

Key Insights

Palindrome Centers: A palindrome has a center that can be a single character (odd length) or between two characters (even length).
Expand Around Center: Start from each possible center and expand outward while characters match.
Two Cases: Check both odd-length (center at i) and even-length (center between i and i+1) palindromes.
DP Bottom-Up: Build from small palindromes to larger ones. A substring is a palindrome if its ends match and the inner substring is a palindrome.
Manacher’s Optimization: Uses previously computed information to avoid redundant comparisons, achieving linear time.