What is the expand-around-centre approach?

Every palindrome is symmetric around its centre. Try each centre in turn — each character for odd lengths and each gap between neighbours for even lengths — and move two pointers outward while the characters at both ends match. The longest stretch found at any centre is the answer.

Why are there 2n − 1 centres?

An odd-length palindrome centres on one of the n characters; an even-length one centres on one of the n − 1 gaps between neighbours. Checking only characters would miss answers like "bb" in "cbbd".

What is the time and space complexity?

O(n²) time: 2n − 1 centres, each expanding at most n/2 steps. O(1) extra space, since only the best start and end are stored. Manacher's algorithm reaches O(n) but is rarely expected in interviews.

Longest Palindromic Substring

Find the longest substring that reads the same both ways by expanding two pointers outward from every possible centre.

MediumSolve on LeetCode

Problem Understanding

Longest Palindromic Substring: given a string s, return its longest substring that reads the same forwards and backwards.

Example: "babad" returns "bab" ("aba" is equally long and also accepted). "cbbd" returns "bb".

Attempt 1: Check Every Substring

There are about n²/2 substrings, and checking each for being a palindrome takes up to n steps: O(n³). The waste is that "abcba" is checked from scratch even though its inside, "bcb", was already known to be a palindrome.

The Intuition: Grow Palindromes From Their Centre

A palindrome is a mirror: if s[lo..hi] is one and s[lo − 1] == s[hi + 1], then s[lo − 1..hi + 1] is one too. So instead of checking substrings, grow palindromes outward from their centre with two pointers moving in opposite directions — the reverse of Valid Palindrome, where they move inward.

There are two kinds of centre:

A character (lo = hi = i) for odd lengths, like "bab".
A gap (lo = i, hi = i + 1) for even lengths, like "bb".

That is 2n − 1 centres. From each, step outward while the ends match; when they stop, the palindrome is s[lo + 1..hi − 1], of length hi − lo − 1. Keep the longest.

Interactive Walkthrough

Each centre is tried in turn. The palindrome grown so far is filled, lo and hi mark the next pair to compare, and a mismatching pair turns red. The frame always surrounds the longest palindrome found so far.

Dry Run Table

Input: "babad"

Centre	Expansion	Stops because	Palindrome	Best
0 `b`	`b`	left end	`"b"`	`"b"`
gap 0–1	—	`b ≠ a`	none	`"b"`
1 `a`	`a` → `bab`	left end	`"bab"`	`"bab"`
gap 1–2	—	`a ≠ b`	none	`"bab"`
2 `b`	`b` → `aba`	`b ≠ d`	`"aba"` (not longer)	`"bab"`
gap 2–3	—	`b ≠ a`	none	`"bab"`
3 `a`	`a`	`b ≠ d`	`"a"`	`"bab"`
gap 3–4	—	`a ≠ d`	none	`"bab"`
4 `d`	`d`	right end	`"d"`	`"bab"`

Return "bab".

The Solution Template

Two centres per index, two pointers stepping outward.

Longest Palindromic Substring Code

1var longestPalindrome = function(s) {
2    let start = 0, end = 0;
3    for (let center = 0; center < s.length; center++) {
4        for (let gap = 0; gap <= 1; gap++) {
5            let lo = center, hi = center + gap;
6            while (lo >= 0 && hi < s.length && s[lo] === s[hi]) {
7                lo--;
8                hi++;
9            }
10            if (hi - lo - 1 > end - start + 1) {
11                start = lo + 1;
12                end = hi - 1;
13            }
14        }
15    }
16    return s.slice(start, end + 1);
17};

Edge Cases & Common Mistakes

One character: it is its own answer; the best starts as s[0].
Even-length answers ("cbbd" → "bb"): skipping the gap centres misses them entirely.
No two equal characters ("abc"): every palindrome has length 1, so the first character is returned.
The whole string ("racecar"): the expansion runs off both ends; the length is still hi − lo − 1.
Off-by-one on return: when the loop stops, s[lo] and s[hi] are not part of the palindrome — it is s[lo + 1..hi − 1].
DP table: dp[i][j] = "is s[i..j] a palindrome" also gives O(n²) time, but O(n²) space.

Summary

Try all 2n − 1 centres — characters and gaps — and expand two pointers outward while the ends match, keeping the longest palindrome seen. O(n²) time, O(1) space.

Valid Palindrome

Container With Most Water