Longest Palindromic Substring LeetCode 5

LeetCode 5, Longest Palindromic Substring, asks you to return the longest contiguous substring of a given string s that reads the same forwards and backwards. For the input "babad", both "bab" and "aba" are valid answers (either is accepted). For "cbbd", the answer is "bb".

A palindrome is a string that equals its reverse. Single characters are trivially palindromes. The challenge is finding the longest one efficiently — the naive O(n^3) approach of checking all substrings is too slow for strings up to length 1000.

This is one of the most commonly asked string problems in technical interviews, appearing at companies like Google, Amazon, and Meta. Understanding the expand-around-center technique and its tradeoffs with dynamic programming and Manacher's algorithm is essential interview preparation.

The brute force approach checks every possible substring and tests if it is a palindrome: O(n^2) substrings, each taking O(n) to verify, giving O(n^3) total — too slow for n=1000 in a timed interview. Dynamic programming improves this: define dp[i][j] = true if s[i..j] is a palindrome. The recurrence is dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]. This runs in O(n^2) time and O(n^2) space, building up from single characters.

While the DP table approach achieves O(n^2) time, it requires O(n^2) extra space for the table. The expand-around-center approach matches the O(n^2) time complexity but uses only O(1) extra space and is simpler to implement — making it strictly better than DP for interviews.

The key insight behind both DP and expand-around-center is that palindromes are defined recursively: a string is a palindrome if its outer characters match and the inner substring is also a palindrome. Expand-around-center exploits this by starting from a center and expanding outward rather than filling a 2D table.

The expand-around-center algorithm iterates over each index i in the string and tries to expand a palindrome centered at i. At each step it compares the characters at the left and right pointers; if they match, it expands further and updates the longest palindrome found.

There are two cases at each index: an odd-length palindrome centered exactly at character i (left = i, right = i), and an even-length palindrome centered between characters i and i+1 (left = i, right = i+1). Both cases must be tried at every position. For "abba", the even-length expansion from between the two b's finds the full palindrome; the odd-length check at each character would only find single-character palindromes in this case.

After each expansion, compare the length of the found palindrome to the current maximum. Track the start index and length (not start and end) to reconstruct the substring at the end. The total work is O(n) centers times O(n) expansion per center in the worst case, giving O(n^2) overall.

A string of length n has exactly 2n-1 possible palindrome centers: n centers at each character position (for odd-length palindromes) and n-1 centers between adjacent characters (for even-length palindromes). For a string of length 5, there are 5 + 4 = 9 possible centers.

The odd centers handle palindromes like "aba" (centered at "b") or "racecar" (centered at "e"). The even centers handle palindromes like "abba" (centered between the two b's) or "noon" (centered between the two o's). Forgetting the even-length case is a common bug that misses all even-length palindromes.

In the worst case (a string of all identical characters like "aaaa"), every possible center produces a palindrome of near-maximum length, requiring O(n) expansion per center. This gives the O(n^2) worst case. For most practical inputs the average expansion is much shorter.

Manacher's algorithm achieves O(n) time by exploiting the symmetry property of palindromes: if a palindrome is centered at c with right boundary r, then any center i within that palindrome has a mirror center i' = 2c - i. The palindrome radius at i is at least min(r - i, radius[i']), allowing reuse of already-computed values.

The algorithm maintains a center c and right boundary r of the rightmost palindrome found so far. For each new center i, it initializes the radius using the mirror value if i is within the current right boundary, then tries to expand further. When expansion goes beyond r, the center and boundary are updated. This amortized O(1) initialization per center gives O(n) total.

Manacher's is rarely asked directly in coding interviews — it is complex to implement correctly under time pressure. However, understanding its principle (reusing computed palindrome lengths via symmetry) deepens your understanding of string algorithms and may come up in system design or algorithm discussions at senior levels.

Python: def longestPalindrome(s): start, maxLen = 0, 1; def expand(l, r): nonlocal start, maxLen; while l >= 0 and r < len(s) and s[l] == s[r]: if r - l + 1 > maxLen: start, maxLen = l, r - l + 1; l -= 1; r += 1; for i in range(len(s)): expand(i, i); expand(i, i + 1); return s[start:start + maxLen]. Time O(n^2), space O(1).

Java: public String longestPalindrome(String s) { int start = 0, maxLen = 1; for (int i = 0; i < s.length(); i++) { int odd = expand(s, i, i); int even = expand(s, i, i + 1); int best = Math.max(odd, even); if (best > maxLen) { maxLen = best; start = i - (best - 1) / 2; } } return s.substring(start, start + maxLen); } private int expand(String s, int l, int r) { while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; } return r - l - 1; }.

Both solutions follow the same structure: an expand helper that returns the length of the longest palindrome centered at (l, r), and a main loop that calls expand for both odd and even centers at each index. The Python version uses nonlocal to update start and maxLen directly; the Java version computes the start from the center index and length after the expansion.

Longest Palindromic Subsequence (LeetCode 516) is closely related but different: a subsequence does not need to be contiguous, so you can delete characters. The answer uses DP: dp[i][j] = longest palindromic subsequence in s[i..j]. This is O(n^2) time and space — there is no expand-around-center equivalent for subsequences.

Valid Palindrome II (LeetCode 680) asks whether you can make a string a palindrome by deleting at most one character. The approach is a two-pointer scan that, when a mismatch is found, checks both the skip-left and skip-right options. Palindrome Partitioning (LeetCode 131) asks for all ways to partition a string into palindromic substrings — solved with backtracking plus expand-around-center or DP preprocessing.

The palindrome family covers a wide range of techniques: two pointers for validity checks, expand-around-center for longest substring, DP interval recurrence for subsequences, and backtracking for partition enumeration. Mastering LeetCode 5 gives you a strong foundation for all palindrome variants.