Pattern visualizer
Longest Palindromic Substring
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. Animated on: Given s="babad", find the longest palindromic substring.
Expand-around-center algorithm
time O(n^2)space O(1)step 1 / 7
b
[0]a
[1]b
[2]a
[3]d
[4]line 2
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 s3 start = 0, maxLen = 14 FOR i from 0 to length of s - 1:5 // odd-length palindromes, center at i6 l = i - 1, r = i + 17 WHILE l >= 0 and r < length of s and s[l] == s[r]: move l one step left, move r one step right8 oddLen = r - l - 19 // even-length palindromes, center between i and i+110 l2 = i, r2 = i + 111 WHILE l2 >= 0 and r2 < length of s and s[l2] == s[r2]: move l2 one step left, move r2 one step right12 evenLen = r2 - l2 - 113 curLen = the larger of oddLen and evenLen14 IF curLen > maxLen: start = i - (curLen / 2 rounded down), maxLen = curLen15 END FOR16 RETURN the substring of s starting at start, maxLen characters long17END FUNCTION
← / → step · space play · Home restart