Find the longest stretch that reads the same both ways. Every palindrome mirrors around a center, a letter or a gap, so try all 2n−1 centers and grow outwards while the ends match, in O(n²) time and O(1) space.
▼The problem
LeetCode 5 (Medium). Given a string s, return its longest palindromic substring (a contiguous stretch that reads the same forwards and backwards).
Examples (LeetCode's): "babad" → "bab" ("aba" is also accepted) and "cbbd" → "bb".
The solution
def longestPalindrome(s):
best = ""
for c in range(2 * len(s) - 1):
l, r = c // 2, (c + 1) // 2
while l >= 0 and r < len(s) and s[l] == s[r]:
l, r = l - 1, r + 1
if r - l - 1 > len(best):
best = s[l + 1:r]
return bestTranscript
Longest Palindromic Substring. Given a string, return its longest stretch that reads the same forwards and backwards.
In B, A, B, A, D, the answer is B A B, though A B A ties it. In C, B, B, D, it's the double B.
The naive way checks every substring: about n squared of them, at up to n steps each. That's order n cubed.
Picture a butterfly instead: every palindrome mirrors around a center. Centers sit on every letter, and on every gap for even lengths: two n minus one in all. From each center, open the wings while both ends match, and keep the widest.
In code, loop over the centers. Start left and right there, and while they're in bounds and the letters match, step outward. Keep the span if it beats the best.
Walk B A B A D. The first B is one letter, and the next gap fails: B and A differ. Centered on the A, the two B's match: B A B, length three. Centered on the middle B, the A's match: A B A, also three. Not longer, so B A B stays, and every later center is shorter.
In C B B D, the gap between the B's matches: B B, length two. Then C and D differ.
Each center expands at most n steps: order n squared time, and constant space. A table, where a substring is a palindrome if its ends match and its inside is one, costs the same time but n squared space.
Pick a center, open the wings, keep the widest. That's Longest Palindromic Substring.