Return the longest substring of s that reads the same forwards and backwards.
"babad" → "bab" (or "aba" — either is accepted)"cbbd" → "bb"
Up to 1,000 characters.
Restating the Problem: You are given a string s. Your job is to find the longest contiguous block of characters within s that reads identically forwards and backwards. We don't just want the length; we need to return the actual string.
Constraints to Note:
s.length is up to 1000. This is a big clue! An O(N^2) algorithm takes about 1,000,000 operations, which easily passes within 1 second.
class Solution: def longestPalindrome(self, s: str) -> str: best_start, best_len = 0, 0 # (1) def expand(lo: int, hi: int): # (2) nonlocal best_start, best_len # (3) while lo >= 0 and hi < len(s) and s[lo] == s[hi]: # (4) lo -= 1 hi += 1 # the loop overshot by one on each side length = hi - lo - 1 # (5) if length > best_len: # (6) best_len = length best_start = lo + 1 for i in range(len(s)): # (7) expand(i, i) # (8) odd centre: one character expand(i, i + 1) # (9) even centre: the gap after it return s[best_start:best_start + best_len] # (10)
ts
function longestPalindrome(s: string): string { let bestStart = 0, bestLen = 0; // (1) function expand(lo: number, hi: number): void { // (2) while (lo >= 0 && hi < s.length && s[lo] === s[hi]) { lo--; hi++; } // (4) const len = hi - lo - 1; // (5) if (len > bestLen) { bestLen = len; bestStart = lo + 1; } // (6) } for (let i = 0; i < s.length; i++) { // (7) expand(i, i); // (8) expand(i, i + 1); // (9) } return s.slice(bestStart, bestStart + bestLen); // (10)}
(1) Remember the best palindrome found so far by where it starts and how long it is, not as a string.
(2) expand(lo, hi) grows a palindrome outward from a middle. Every palindrome is a mirror around its centre. So start at a centre and step outward while the two ends match.
(3) nonlocal lets the inner function change the two outer variables. Without it, assigning to best_len inside expand would create a new, separate variable.
(4) While both ends are inside the string and the two characters match, step both ends outward by one.
(5) The loop stops one step too far on each side. Either a pointer left the string, or the two characters did not match. So the palindrome is the stretch strictly between lo and hi, and its length is hi - lo - 1.
(6) A new longest palindrome. It starts at lo + 1, one step inside the overshoot.
(7) Try every position as a centre.
(8) An odd-length palindrome centred on one character, like "aba" around the b.
(9) An even-length palindrome centred on the gap after it, like "abba" around the middle gap. If the two characters differ, this returns at once with length 0.
(10) Cut the answer out once, at the end.
The off-by-one after the loop is the fiddly part, so derive it rather than guess. The while stops when the characters no longer match, which means lo and hi have each moved one step too far. The palindrome actually spans lo + 1 to hi - 1, and its length is (hi - 1) - (lo + 1) + 1 = hi - lo - 1.
expand(i, i + 1) handles the even case, and it needs no bounds check — if i + 1 is past the end, the while condition fails immediately and the length comes out as 0.
Track indices, not substrings. Slicing inside the loop would be O(n) per check and would make the whole thing O(n^3). This is the same discipline as 4.6.5.
Time Complexity Derivation: We loop through n characters. At each character, we consider 2 centres (the odd and the even). That gives 2n - 1 centres to check. For each centre, the while loop expands outward until a mismatch is found. In the worst case (e.g., "aaaaa"), a centre expands up to n/2 steps. Therefore, (2N) \times (N/2) = N^2, making the total time O(N^2).
Space Complexity Derivation: We only store two integer variables: best_start and best_len. The expand function just uses local integer variables lo and hi. No auxiliary arrays or hash maps are allocated. Thus, O(1) extra space. This is the real advantage over the DP version below.
The ends match, and the inside is already known to be a palindrome. The j - i < 2 covers lengths 1 and 2, which have no inside.
python
n = len(s)dp = [[False] * n for _ in range(n)]best = (0, 1)for j in range(n): for i in range(j, -1, -1): # i counts DOWN if s[i] == s[j] and (j - i < 2 or dp[i+1][j-1]): dp[i][j] = True if j - i + 1 > best[1]: best = (i, j - i + 1)return s[best[0]:best[0] + best[1]]
The loop order is the whole difficulty.dp[i][j] reads dp[i+1][j-1] — a largeri and a smallerj — so i must count downwards while j counts upwards, or you read cells that are not filled yet. That ordering question is the thing 2-D DP is really about, and it is covered properly in 4.24.
O(n^2) time and O(n^2) space.
Same time, far more memory, more code, and an ordering trap. Centre expansion wins on every count. Write it, and mention the DP as the version that generalises — because the table is genuinely useful in 4.18.7 Palindrome Partitioning, where you need to test many substrings rather than find one.
That is the real lesson: precompute a table when you will query it repeatedly; expand from centres when you need one answer.
There is an O(n) solution. It runs centre expansion but reuses information from palindromes already found, so a centre inside a known palindrome starts from a lower bound instead of from zero — the same "the pointer only moves forward" argument as the sliding window and the monotonic stack.
It is intricate and almost never expected. Name it, say it is O(n), and move on.4.31 builds it properly.
Palindromic Substrings — count them all instead of finding the longest. The identical expansion with a counter. 4.23.6.
Longest Palindromic Subsequence — a completely different problem, because gaps are allowed. It is genuinely 2-D DP, and it equals the longest common subsequence of the string and its reverse. 4.24.
Palindrome Partitioning II — the fewest cuts, which needs the DP table.
Substring means no gaps; subsequence allows gaps. Confusing them changes the algorithm completely, so read the problem statement twice.
"How many centres are there?"2n − 1. Explain the even case, and say what "cbbd" does to a solution that misses it.
"Derive the length after expansion." The loop overshoots by one on each side, so it is hi - lo - 1.
"Can you do better than O(n^2)?" Manacher's, O(n). Naming it is enough.
"Why not DP?" Same time, O(n^2) space instead of O(1), and a loop-order trap. Then say when the table is worth building.
"What about the longest palindromic subsequence?" Different problem — 2-D DP, and it is LCS with the reversed string.
One thing to volunteer: say the centre count and the even-centre case before writing anything. It is the one place this problem is designed to catch you.