Longest Palindromic Substring - Video Solutions

Problem Overview: Given a string s, return the longest substring that reads the same forward and backward. The substring must be continuous. You need to scan the string and detect the largest window where characters mirror around a center.

Approach 1: Expand Around Center (O(n^2) time, O(1) space)

A palindrome mirrors around its center. For each index in the string, treat it as the center of a palindrome and expand outward using two pointers. Handle both odd-length palindromes (center = i) and even-length palindromes (center = i, i+1). While the characters at the left and right pointers match, expand further and update the best substring length.

This method iterates through the string once and performs expansion at each position. In the worst case (like "aaaaa"), every expansion scans many characters, leading to O(n^2) time. The advantage is constant extra memory since only indices are tracked. This approach relies heavily on Two Pointers applied to a String. Most production implementations and interview solutions use this technique because it is simple and memory efficient.

Approach 2: Dynamic Programming (O(n^2) time, O(n^2) space)

Dynamic programming stores whether each substring is a palindrome. Create a 2D table dp[i][j] that represents whether substring s[i..j] is palindromic. A substring is a palindrome if the characters match (s[i] == s[j]) and the inner substring s[i+1..j-1] is also a palindrome.

Initialize base cases for length 1 and length 2 substrings. Then iterate over substring lengths from 3 to n. Whenever dp[i][j] becomes true, update the longest range. The table ensures each substring state is computed once, giving O(n^2) time. However, the memory footprint is also O(n^2), which can be significant for long strings. This approach demonstrates classic Dynamic Programming where overlapping subproblems are reused.

Recommended for interviews: Expand Around Center is the expected solution in most coding interviews. It achieves optimal practical performance with O(1) extra space and straightforward logic. Dynamic Programming proves you understand palindrome substructure but uses unnecessary memory. A strong candidate usually explains the brute-force idea, then moves quickly to the center-expansion technique.