LeetCode 5: Longest Palindromic Substring | Optimal Solutions in Python & JS

Longest Palindromic Substring - LeetCode Problem 5

Difficulty: Medium

Problem Statement

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

Example

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

Approach 1: Expand Around Center (Optimal - O(n²) Complexity)

Since a palindrome mirrors around its center, we can expand around each character (odd-length) and each pair (even-length).

Python Solution:

def longest_palindrome(s: str) -> str:
    if not s:
        return ""
    
    start, max_length = 0, 0
    
    def expand_around_center(left, right):
        nonlocal start, max_length
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left + 1 > max_length:
                start, max_length = left, right - left + 1
            left -= 1
            right += 1

    for i in range(len(s)):
        expand_around_center(i, i)   # Odd length palindrome
        expand_around_center(i, i+1) # Even length palindrome
    
    return s[start:start + max_length]
    

JavaScript Solution:

function longestPalindrome(s) {
    if (!s) return "";
    
    let start = 0, maxLength = 0;

    function expandAroundCenter(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            if (right - left + 1 > maxLength) {
                start = left;
                maxLength = right - left + 1;
            }
            left--;
            right++;
        }
    }

    for (let i = 0; i < s.length; i++) {
        expandAroundCenter(i, i);   // Odd length palindrome
        expandAroundCenter(i, i + 1); // Even length palindrome
    }

    return s.substring(start, start + maxLength);
}
    

Time Complexity Analysis

The Expand Around Center approach checks all centers and expands outward, resulting in O(n²) complexity.

Alternative Approach: Dynamic Programming (O(n²))

The dynamic programming approach builds a 2D table where dp[i][j] = True if s[i:j+1] is a palindrome.

Python DP Solution:

def longest_palindrome_dp(s: str) -> str:
    n = len(s)
    if n <= 1:
        return s

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

    for i in range(n):
        dp[i][i] = True  # Single character is a palindrome

    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2 or dp[i + 1][j - 1]:
                    dp[i][j] = True
                    if length > max_length:
                        start, max_length = i, length

    return s[start:start + max_length]
    

Conclusion

• Expand Around Center is simpler and works efficiently for most cases.
• Dynamic Programming is another option but requires extra space.

Use the Expand Around Center approach for better performance in interviews and real-world applications.