A palindrome is a string that reads the same forwards and backwards, like "racecar" or "abba". Finding the longest palindromic substring is a classic algorithmic problem that demonstrates the power of the "expand around center" approach.
The key insight is that every palindrome has a center. For odd-length palindromes like "racecar", the center is the middle character. For even-length palindromes like "abba", the center is between the two middle characters. Once you identify a potential center, you can expand outward, comparing characters on both sides.
The expand around center technique works by:
This approach is efficient because it avoids the need to check every possible substring explicitly. Instead of examining all O(n²) substrings individually, you expand from each center, giving you O(n²) time complexity in the worst case but with much better practical performance.
The algorithm handles both odd and even length palindromes by checking two cases at each position: expanding around the character itself (odd-length) and expanding around the gap between the character and the next one (even-length). This ensures no palindromes are missed.
When multiple palindromes have the same maximum length, the algorithm naturally finds the leftmost one first due to the left-to-right iteration through potential centers.
1def find_palindrome_at_center(s, left, right):
2 # Expand while characters match
3 while left >= 0 and right < len(s) and s[left] == s[right]:
4 left -= 1
5 right += 1
6
7 # Return the valid palindrome
8 return s[left + 1:right]
9
10# Example usage:
11text = "abacabad"
12print(find_palindrome_at_center(text, 3, 3)) # "aca" - odd center
13print(find_palindrome_at_center(text, 2, 4)) # "acaba" - expanding from middle