LeetCode 5: Longest Palindromic Substring

Problem Description

LeetCode Problem 5

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.

Difficulty: Medium

Tags: two pointers, string, dynamic programming

Rating: 94.21%

Complexity Analysis

The solution has the following complexity characteristics:

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

Solution

Here’s my Python solution to this problem:

#Problem 5: Longest Palindromic Substring

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

        def expand(l, r):
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            return l + 1, r - 1

        l = r = 0

        for i in range(n):
            #Odd length
            l1, r1 = expand(i, i)
            if r1-l1 > r-l:
                l, r = l1, r1
            
            #Even length
            l1, r1 = expand(i, i+1)
            if r1-l1 > r-l:
                l, r = l1, r1
        
        return s[l:r+1]

Why This Solution is Better Than Dynamic Programming

While both dynamic programming and expand-around-center approaches solve the Longest Palindromic Substring problem, the expand-around-center approach offers several significant advantages:

1. Space Complexity

• Expand-around-center: O(1)
  • Only uses a constant amount of extra space
  • Maintains just a few variables regardless of input size
• Dynamic Programming: O(n²)
  • Requires a 2D DP table of size n×n
  • For a string of length 1000, needs a million boolean values

2. Implementation Simplicity

• Expand-around-center:
  • More intuitive and easier to understand
  • Fewer edge cases to handle
  • Simpler code maintenance
• Dynamic Programming:
  • Requires careful handling of table initialization
  • More complex state transitions
  • Higher chance of implementation errors

3. Early Termination

• Expand-around-center:
  • Can stop expanding when no longer palindromic
  • More efficient for strings with short palindromes
• Dynamic Programming:
  • Must fill the entire table regardless of palindrome length
  • No opportunity for early optimization

Time Complexity Analysis

Both approaches have O(n²) time complexity in the worst case, but the expand-around-center method:

• Has better average-case performance
• Uses fewer operations per iteration
• Has better constant factors
• More efficient for common cases where palindromes are relatively short