LeetCode 5: Longest Palindromic Substring

Problem Description

There’s also longest palindromic subsequence problem.

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%

Understanding the Problem

Before jumping into the solution, let’s understand what makes this problem interesting:

1. A palindrome reads the same forwards and backwards (like “racecar”)
2. We need to consider both odd-length palindromes (like “aba”) and even-length palindromes (like “bb”)
3. We want the longest such substring, and if there are ties, any valid answer is acceptable

Solution Approach: Expand Around Center

While this problem can be solved using dynamic programming, I’ll use the expand-around-center approach, which is more efficient in terms of space complexity and often more intuitive to understand.

Here’s my Python solution:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s: return ""
        n = len(s)
        
        def expand(l: int, r: int) -> tuple[int, int]:
            # Expand around center while characters match
            while l >= 0 and r < n and s[l] == s[r]:
                l -= 1
                r += 1
            # Return the valid palindrome boundaries
            return l + 1, r - 1
        
        # Track the longest palindrome boundaries
        l = r = 0
        
        # Try each possible center position
        for i in range(n):
            # Check odd length palindromes
            l1, r1 = expand(i, i)
            if r1 - l1 > r - l:
                l, r = l1, r1
            
            # Check even length palindromes
            l1, r1 = expand(i, i + 1)
            if r1 - l1 > r - l:
                l, r = l1, r1
        
        return s[l:r + 1]

Detailed Walkthrough

Let’s walk through how this solution works using the example string “babad”:

1. Initial state:

   • String: “babad”
   • Current longest palindrome: "" (empty)

2. Starting with center at ‘b’ (index 0):

   • Odd length: expand(0, 0) tries “b” → palindrome of length 1
   • Even length: expand(0, 1) tries “ba” → not a palindrome
   • Current longest: “b”

3. Center at ‘a’ (index 1):

   • Odd length: expand(1, 1) tries “a”, then “bab” → palindrome of length 3
   • Even length: expand(1, 2) tries “ab” → not a palindrome
   • Current longest: “bab”

4. Center at ‘b’ (index 2):

   • Odd length: expand(2, 2) tries “b”, then “aba” → palindrome of length 3
   • Even length: expand(2, 3) tries “ba” → not a palindrome
   • Current longest: “bab” (we keep first occurrence when lengths are equal)

5. Center at ‘a’ (index 3):

   • Odd length: expand(3, 3) tries “a” → palindrome of length 1
   • Even length: expand(3, 4) tries “ad” → not a palindrome
   • Current longest: “bab”

6. Center at ‘d’ (index 4):

   • Odd length: expand(4, 4) tries “d” → palindrome of length 1
   • Even length: expand(4, 5) → out of bounds
   • Final longest: “bab”

Performance Analysis

Time Complexity: $O(n²)$

• We try each position as a center: O(n)
• For each center, we might expand up to the full string length: O(n)

Space Complexity: $O(1)$

• We only use a constant amount of extra space
• The output string is not counted in space complexity