DSA AnimatorDSA animations
Longest Palindromic Substring LC #5 Medium Expand Around Center
Problem

Given a string s, return the longest palindromic substring in s.

Example 1
Input: s = "babad"
Output: "bab"
Constraints: 1 ≤ s.length ≤ 1000  |  s consists of digits and English letters.
Try Examples
Custom:
Approach
Expand Around Center
For each index i, treat it as the center of an odd-length palindrome (l=r=i) and each pair (i, i+1) as an even-length center. Grow l left and r right while s[l]==s[r]. Track the longest span. O(n²) time, O(1) space.
① Intro
›
② Odd centers
›
③ Even centers
›
④ Done
s[l]—
?
s[r]—
status—
Ready
Press Play to begin.
Best palindrome so far
Variables
i
—
l
—
r
—
maxLen
—
Step Logic
Press ▶ Play or Next Step to begin.
🎉
—
Longest palindromic substring
Ready 0 / 0
Select an example and press Play.
Algorithm
1
Initialize start=0, maxLen=1 (single char is a palindrome)
2
For each index i, expand odd center (i,i) and even (i,i+1)
3
While s[l]==s[r], grow l--, r++; record palindrome length
4
If longer than maxLen, update start and maxLen
Time
O(n²)
Space
O(1)
Why It Works

Why centers? Every palindrome has a center: one character (odd length) or between two characters (even length). Trying all n odd and n−1 even centers covers every substring that can be a palindrome.

Why expand? If s[l..r] is a palindrome and s[l-1]==s[r+1], then s[l-1..r+1] is also a palindrome. We greedily expand until characters differ or we leave the string.

Why O(n²)? O(n) centers × up to O(n) expansion steps each.

How to solve Longest Palindromic Substring

LeetCode 5 · Medium · Strings · Pattern: Expand Around Center

Why the obvious approach is slow

Building every substring and checking whether it is a palindrome is O(n) cubed. That is far too slow.

The key idea

Every palindrome has a center. Treat each index as a center, and expand to both sides while the two ends match. But note that a palindrome like b b has its center between two characters. So expand twice at every index: once from a single character, and once from the gap after it.

Remember

Expand around 2 n −1 centers, both odd and even. Keep only the longest expansion.

Run the animation above on your own input, or watch the 1:41 video explanation of Longest Palindromic Substring with a dry run and Java code.

More Strings problems