DSA Tracker

Visualize

Longest Palindromic Substring

Expand-around-center algorithm

time O(n^2)space O(1)

A palindrome is symmetric around some middle point, so every palindromic substring can be found by picking that center and growing outward — the instant the two sides stop matching, you've found the largest palindrome that center can produce. Checking every possible center (each character for odd-length palindromes, each gap between characters for even-length ones) and expanding outward from each guarantees none get missed. Track the longest one found across all centers.

Details

Animated on: Given s="babad", find the longest palindromic substring

Problem:Longest Palindromic SubstringMedium

Expand-around-center algorithm

step 1 / 7

b
[0]
a
[1]
b
[2]
a
[3]
d
[4]

Initial string s='babad' as array. Indices 0-4. Will check each center position for palindromes.

Pseudocode
1FUNCTION longestPalindrome(s):
2  IF length of s < 2: RETURN s
3  start = 0, maxLen = 1
4  FOR i from 0 to length of s - 1:
5    // odd-length palindromes, center at i
6    l = i - 1, r = i + 1
7    WHILE l >= 0 and r < length of s and s[l] == s[r]: move l one step left, move r one step right
8    oddLen = r - l - 1
9    // even-length palindromes, center between i and i+1
10    l2 = i, r2 = i + 1
11    WHILE l2 >= 0 and r2 < length of s and s[l2] == s[r2]: move l2 one step left, move r2 one step right
12    evenLen = r2 - l2 - 1
13    curLen = the larger of oddLen and evenLen
14    IF curLen > maxLen: start = i - (curLen / 2 rounded down), maxLen = curLen
15  END FOR
16  RETURN the substring of s starting at start, maxLen characters long
17END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 7 steps
  1. Initial string s='babad' as array. Indices 0-4. Will check each center position for palindromes.
  2. Center i=0 (char 'b'). Odd expansion: l=-1, r=1. s[-1] out of bounds, stop. Odd palindrome 'b', length 1. Even expansion: l2=0, r2=1. s[0]='b' vs s[1]='a', mismatch, stop. Even palindrome '', length 0. Best so far: 'b' (len 1).
  3. Center i=1 (char 'a'). Odd expansion: l=0, r=2. s[0]='b' === s[2]='b', match! Expand: l=-1, r=3. s[-1] out of bounds, stop. Odd palindrome 'bab', length 3. Even expansion: l2=1, r2=2. s[1]='a' vs s[2]='b', mismatch, stop. Even palindrome '', length 0. Best so far: 'bab' (len 3).
  4. Center i=2 (char 'b'). Odd expansion: l=1, r=3. s[1]='a' === s[3]='a', match! Expand: l=0, r=4. s[0]='b' vs s[4]='d', mismatch, stop. Odd palindrome 'aba', length 3. Even expansion: l2=2, r2=3. s[2]='b' vs s[3]='a', mismatch, stop. Even palindrome '', length 0. Best so far: 'bab' or 'aba' (len 3, tie).
  5. Center i=3 (char 'a'). Odd expansion: l=2, r=4. s[2]='b' vs s[4]='d', mismatch, stop. Odd palindrome 'a', length 1. Even expansion: l2=3, r2=4. s[3]='a' vs s[4]='d', mismatch, stop. Even palindrome '', length 0. Best remains 'bab'/'aba' (len 3).
  6. Center i=4 (char 'd'). Odd expansion: l=3, r=5 out of bounds, stop. Odd palindrome 'd', length 1. Even expansion: l2=4, r2=5 out of bounds, stop. Even palindrome '', length 0. Best remains 'bab'/'aba' (len 3).
  7. All centers checked. i=1 finds 'bab' (length 3) first; i=2's 'aba' ties it but doesn't beat it, so the algorithm keeps 'bab'. Return s.slice(0,3) = 'bab'.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Longest Palindromic Substring in the editorAll Strings problemsBack to roadmap