Finding the longest palindromic substring is a classic interview problem. While the naive approach takes $O(N^3)$ and dynamic programming takes $O(N^2)$, Manacher's Algorithm achieves the same result in linear time ($O(N)$).
The Core Concept: Symmetry and Re-use
Manacher's algorithm avoids redundant work by leveraging the symmetry of palindromes. If we know a palindrome exists at a certain center, we can use its properties to estimate the palindrome lengths of its mirrored positions.
Key Steps:
- Pre-processing: Insert special characters (like
#) between every character to handle both even and odd-length palindromes uniformly. - Center and Right Boundary: Keep track of the center of the rightmost palindrome found so far and its right boundary.
- Mirroring: For a new position, use its mirror across the current center to initialize its palindrome radius.
Manacher's Algorithm Implementation in Java
public class Manacher {
public String longestPalindrome(String s) {
if (s == null || s.length() == 0) return "";
// Step 1: Pre-process the string
StringBuilder sb = new StringBuilder();
sb.append("^");
for (char c : s.toCharArray()) {
sb.append("#").append(c);
}
sb.append("#$");
String t = sb.toString();
int n = t.length();
int[] p = new int[n];
int center = 0, right = 0;
for (int i = 1; i < n - 1; i++) {
int mirror = 2 * center - i;
if (i < right) {
p[i] = Math.min(right - i, p[mirror]);
}
// Attempt to expand palindrome centered at i
while (t.charAt(i + (1 + p[i])) == t.charAt(i - (1 + p[i]))) {
p[i]++;
}
// Update center and right boundary if expanded past right
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
}
// Find the maximum radius and its center
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (p[i] > maxLen) {
maxLen = p[i];
centerIndex = i;
}
}
int start = (centerIndex - maxLen) / 2;
return s.substring(start, start + maxLen);
}
}
Why use Manacher's?
| Feature | Manacher's | Dynamic Programming | Naive Approach |
|---|---|---|---|
| Time Complexity | $O(N)$ | $O(N^2)$ | $O(N^3)$ |
| Space Complexity | $O(N)$ | $O(N^2)$ | $O(1)$ |
| Best For | Large strings | Small strings | Quick implementation |
Real-World Applications
- Bioinformatics: Finding palindromic sequences in DNA, which often indicate binding sites for proteins.
- Data Compression: Identifying repeating patterns in strings for more efficient encoding.
- Text Processing: Advanced search and pattern matching in large text corpora.
Summary
Manacher's algorithm is a brilliant example of how a small amount of pre-processing and a clever use of symmetry can transform a quadratic problem into a linear one. While the logic is more intricate than standard string algorithms, its performance is unmatched for palindrome-related tasks. Mastering this algorithm is a surefire way to stand out in high-level technical interviews.
