Course contentsShow
← Computer Science
Lesson 936 of 2,87222. Dynamic ProgrammingFree lesson

Longest Palindromic Substring

Identify the longest contiguous palindromic substring using expand-around-center with DP optimization.

Longest Palindromic Substring

You'll learn how to find the longest contiguous palindrome inside a string by expanding around each potential center, optionally using dynamic programming to optimize the process.

The Core Idea

Unlike finding the longest palindromic subsequence (where characters don't need to be adjacent), finding the longest palindromic substring requires all characters to be contiguous—they must appear side-by-side in the original string.

The expand-around-center approach works like this: treat each character (and each pair of adjacent characters) as a potential "center" of a palindrome, then expand outward while characters match. This naturally finds contiguous palindromes.

Why Two Types of Centers?

Palindromes can have:

  • Odd length: single-character center (like "racecar" centers on 'e')
  • Even length: two-character center (like "abba" centers between 'b' and 'b')

You must check both cases for each position.

DP Optimization

While expand-around-center already runs efficiently (O(n²) time), you can integrate DP by building a table dp[i][j] that stores whether substring from index i to j is a palindrome. This avoids re-checking the same substrings:

  • Base case: single characters are palindromes
  • Transition: dp[i][j] = (s[i] == s[j]) AND dp[i+1][j-1]

This table lets you query any substring's palindrome status in constant time after preprocessing.

The Process

  1. For each position, expand around it (both odd and even centers)
  2. Track the longest palindrome found so far
  3. Optionally use a DP table to cache results and avoid redundant checks

Key Takeaway: The longest palindromic substring is found by checking every possible center in the string and expanding outward while characters match, optionally caching results with DP to avoid redundant work.