LeetEye LeetEye
Medium 1D Dynamic Programming ~5 min

Longest Palindromic Substring

1d-dp longest-palindromic-substring

Problem

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

Examples

Example 1
Input: s = "babad"
Output: "bab" (or "aba")
Example 2
Input: s = "cbbd"
Output: "bb"
Key Insight

Expand around center: every palindrome has a center (one char for odd length, two chars for even length).

Every palindrome has a center. Try all 2n-1 centers, expand outward while characters match. Track longest.

How to Approach This Problem

Pattern Recognition: When you see keywords like longest palindromic substring 1d-dp, think 1D Dynamic Programming.

Step-by-Step Reasoning

1 "aba" has center at:
Answer: 'b' (index 1)
Odd-length palindromes have a single character center.
2 "abba" has center:
Answer: Between the two 'b's
Even-length palindromes have center between two characters.
3 For string of length n, total possible centers:
Answer: 2n - 1
n single-char centers + (n-1) between-char centers = 2n - 1.
4 When expanding from center (left, right):
Answer: Expand if s[left] == s[right]
Keep expanding while characters match. Stop when mismatch or boundary.
5 Expand around center vs DP:
Answer: Expand is O(n²) time, O(1) space
Expand around center is more space-efficient for this problem.

Solution

def longestPalindrome(s: str) -> str:
    result = ""
    
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]
    
    for i in range(len(s)):
        # Odd length palindrome (single char center)
        odd = expand(i, i)
        if len(odd) > len(result):
            result = odd
        
        # Even length palindrome (between chars center)
        even = expand(i, i + 1)
        if len(even) > len(result):
            result = even
    
    return result

Complexity Analysis

Time O(n²)
Space O(1)

Master This Pattern

Build intuition with interactive MCQs. Practice 1D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye