AlgoViz
HomeStrings

Longest Palindromic Substring

Medium

Expand around every centre

Problem

Return the longest substring of a string that is a palindrome.

In simple words

Treat each spot as a mirror centre and expand outwards while both sides match.

The idea

Every palindrome has a centre, either a character or a gap between two characters, so try all 2n-1 centres and expand outward while the characters match. It is O(n²) with O(1) space, which is simpler and usually faster in practice than the DP table.

The trick

  • 2n-1 centres: n single characters plus n-1 gaps, to catch even-length palindromes.
  • Track the best start and length rather than building substrings as you go.
  • Manacher's algorithm gets it to O(n) if you need it.
b
a
b
a
d
0
1
2
3
4

Step 1 of 17. Brute force: check every substring — is it a palindrome? keep the longest. Values: b, a, b, a, d.

1/17
Brute force
timeO(n³)spaceO(1)

Check every substring.

1for (let i = 0; i < n; i++)2  for (let j = i; j < n; j++)3    if (isPalindrome(s, i, j) && j - i + 1 > best.length)4      best = s.slice(i, j + 1);

Input

array
[b, a, b, a, d]

Output

longest
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
s = "babad"
Output:
"bab"
Explanation:
"bab" reads the same both ways ("aba" also valid).

Example 2

Input:
s = "cbbd"
Output:
"bb"
Explanation:
The middle "bb" is the longest mirror.

Example 3

Input:
s = "a"
Output:
"a"
Explanation:
A single letter is its own palindrome.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.