Longest Palindromic Substring - Solution & Explanation

Problem Overview: Given a string s, return the longest substring that reads the same forward and backward. The substring must be contiguous, so you cannot rearrange characters or skip indices.

This problem sits at the intersection of string manipulation and palindrome detection. The challenge is checking all possible centers efficiently without recomputing the same substrings repeatedly.

Approach 1: Expand Around Center (Time: O(n²), Space: O(1))

A palindrome mirrors around its center. Every palindrome can have either one center (odd length like aba) or two centers (even length like abba). Iterate through the string and treat each index as a potential center. Expand outward using two pointers while the characters match.

For each index i, run two expansions: one with (i, i) for odd-length palindromes and another with (i, i+1) for even-length palindromes. Track the longest substring found during these expansions. Each expansion moves the two pointers outward until the characters differ or boundaries are reached.

This approach avoids storing intermediate states and checks only meaningful palindrome candidates. In the worst case (e.g., aaaaa) each expansion scans many characters, leading to O(n²) time, but the constant factors are small and memory usage stays O(1).

Approach 2: Dynamic Programming (Time: O(n²), Space: O(n²))

The dynamic programming approach builds a table dp[i][j] indicating whether substring s[i..j] is a palindrome. Single characters are palindromes, and pairs of equal characters form length-2 palindromes. For longer substrings, a substring is a palindrome if s[i] == s[j] and dp[i+1][j-1] is true.

Fill the DP table by increasing substring length. Each time a palindrome is confirmed, update the longest substring indices. This method ensures every substring is evaluated exactly once.

The main advantage is clarity: the palindrome property is expressed directly through subproblems. The downside is memory usage, since the DP table requires O(n²) space. For long strings this becomes expensive compared to the center-expansion approach.

Recommended for interviews: Expand Around Center is the solution most interviewers expect. It demonstrates understanding of palindrome symmetry and avoids unnecessary memory. Dynamic Programming shows strong problem decomposition but is rarely preferred due to its O(n²) space cost. Mentioning Manacher’s algorithm (O(n) time) can earn bonus points, though implementing it correctly during interviews is uncommon.