"b"
best
Every palindrome has a center — either one character (odd length) or a gap between two equal characters (even length). Expand outward from each of the 2n − 1 possible centers and track the widest match seen, yielding an O(n²) solution with O(1) extra space.
Given string s, return the longest contiguous substring that reads the same forwards and backwards. For s="babad" the answer is "bab" (or "aba" — both length 3 are valid). For s="cbbd" the answer is "bb". Palindromes are everywhere: DNA reverse complements, string hashing, and a dozen interview follow-ons all hinge on this primitive.
bestL = bestR = 0 (the single first character is the trivial palindrome). This avoids a special-case for empty or length-1 input.expand(l, r). While l >= 0, r < n, and s[l] === s[r]: update best if this window is wider, then decrement l and increment r. O(n) in the worst case per center.expand(i, i) for the odd-length center (a single character always palindromes) and expand(i, i+1)for the even-length center (the gap; the while loop won't enter if s[i] !== s[i+1], so it's safe).s.slice(bestL, bestR + 1)."b" and "b" in "cbbd" must be seeded with expand(i, i+1), not expand(i, i). Many candidates code only the odd case and fail on inputs like "bb" or "abbc".Manacher's uses previously computed palindrome radii to skip redundant expansions, achieving O(n)time. It's interview-overkill for most settings — learn the idea, but code expand-around-center in practice.
"babad". We will try every center — 5 odd + 4 even — and expand outward to find the longest palindromic substring.function longestPalindrome(s: string): string {
let bestL = 0, bestR = 0;
function expand(l: number, r: number): void {
while (l >= 0 && r < s.length && s[l] === s[r]) {
if (r - l > bestR - bestL) { bestL = l; bestR = r; }
l--;
r++;
}
}
for (let i = 0; i < s.length; i++) {
expand(i, i); // odd-length centers
expand(i, i + 1); // even-length centers (the gap between i and i+1)
}
return s.slice(bestL, bestR + 1);
}bestL and bestR as character indices rather than the substring itself to avoid repeated string allocation during expansion.r - l > bestR - bestL compares spans so no Math.abs needed.i, fire two seeds: expand(i, i) for odd-length (single-char center) and expand(i, i+1) for even-length (character-gap center). The even call safely no-ops if s[i] !== s[i+1].s.slice(bestL, bestR + 1) is O(k) where k is the answer length; this is unavoidable since we must materialize the string.| "longest palindromic…" or "find palindrome in string" | expand around center |
| even-length palindrome case (e.g. "bb", "abba") | seed with expand(i, i+1) |
| O(1) space string symmetry check | two outward pointers from a pivot |
| count/find all palindromic substrings | same expand loop, add a counter |
function longestPalindrome(s: string): string {
let bestL = 0, bestR = 0;
function expand(l: number, r: number): void {
while (l >= 0 && r < s.length && s[l] === s[r]) {
if (r - l > bestR - bestL) { bestL = l; bestR = r; }
l--; r++;
}
}
for (let i = 0; i < s.length; i++) {
expand(i, i); // odd
expand(i, i + 1); // even
}
return s.slice(bestL, bestR + 1);
}2n − 1: n odd-length centers (each character) + n−1 even-length centers (each gap between adjacent characters).s="cbbd", what is the answer and which center produces it?expand(i, i+1) do when s[i] !== s[i+1]?s="racecar". Which center yields the longest palindrome?