Write a function to find the longest palindrome in a string.
2026 Update: Longest Palindrome — Character Frequency Approach
There are two distinct palindrome problems: (1) Longest palindromic substring — contiguous characters; (2) Longest palindrome you can build from given characters. They use completely different approaches.
from collections import Counter
# Problem 1: Longest palindrome BUILDABLE from given characters (LeetCode #409)
def longest_palindrome_buildable(s: str) -> int:
"""
Use characters of s to build the longest palindrome.
Each even-count character can be used fully.
Each odd-count character can be used (count-1) letters, plus
one odd-count character can be placed in the center.
"""
counts = Counter(s)
length = 0
has_odd = False
for count in counts.values():
length += count if count % 2 == 0 else count - 1
if count % 2 == 1:
has_odd = True
return length + (1 if has_odd else 0)
# Problem 2: Longest palindromic SUBSTRING (contiguous) — expand around center
def longest_palindromic_substring(s: str) -> str:
start = end = 0
def expand(l: int, r: int) -> int:
while l >= 0 and r end - start:
start = i - (max_len - 1) // 2
end = i + max_len // 2
return s[start:end + 1]
# Problem 3: Minimum insertions to make string a palindrome
def min_insertions_to_palindrome(s: str) -> int:
"""
Equivalent to: len(s) - len(LCS(s, reverse(s))).
Uses DP for LCS.
"""
r = s[::-1]
n = len(s)
dp = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, n + 1):
if s[i-1] == r[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
lcs_len = dp[n][n]
return n - lcs_len
# Test all three
print(longest_palindrome_buildable("aabbccc")) # 7: "abccba" + one 'c' center = "abcccba"
print(longest_palindromic_substring("babad")) # "bab" or "aba"
print(min_insertions_to_palindrome("abcba")) # 0 (already palindrome)
print(min_insertions_to_palindrome("abcd")) # 3: insert "dcb" -> "abcddcba" or similar
Know which problem you’re solving: “Longest palindrome from characters” = frequency analysis, O(n). “Longest palindromic substring” = expand around center, O(n²). “Make palindrome with min insertions” = LCS-based DP, O(n²). Confusing these three in interviews is a common mistake. LeetCode #409, #5, #1312.