Daily DSA: Linear Time Longest Palindrome (Hard)
Problem Statement
Given a string s of length up to $10^6$, find the longest substring that is a palindrome. A palindrome is a string that reads the same forward and backward.
While this problem is often solved in $O(N^2)$ using Dynamic Programming or Center Expansion, the constraints here require a linear time $O(N)$ solution.
Examples
Example 1:
- Input:
s = "babad" - Output:
"bab" - Explanation:
"aba"is also a valid answer.
Example 2:
- Input:
s = "cbbd" - Output:
"bb"
Example 3:
- Input:
s = "a" - Output:
"a"
Constraints
1 <= s.length <= 1,000,000sconsists of lowercase English letters.- Time Limit: 1.0s
Approach: Manacher’s Algorithm
Manacher’s Algorithm is a sophisticated approach to find all palindromic radii in linear time.
-
Preprocessing: Palindromes can be odd-length (
aba) or even-length (abba). To handle both uniformly, we transform the string by inserting a special character (like#) between every character and at both ends. For example,ababecomes#a#b#a#(length 7) andabbabecomes#a#b#b#a#(length 9). Every palindrome in the transformed string now has an odd length. - State Variables:
P[i]: The radius of the palindrome centered at indexiin the transformed string.C: The center of the palindrome that reaches the furthest to the right.R: The right boundary of this palindrome (R = C + P[C]).
- Mirroring: For a current index
i, we find its mirror indexi_mirror = 2*C - irelative to the current centerC.- If
i < R, we can initializeP[i]asmin(R - i, P[i_mirror]). This is the core optimization that avoids redundant character comparisons. - We then attempt to expand around
imanually. - If the expanded palindrome centered at
igoes beyondR, we updateC = iandR = i + P[i].
- If
- Extracting Result: The maximum value in
Pcorresponds to the length of the longest palindrome in the original string. The starting index can be derived from the position in the transformed string.
Complexity Analysis
- Time Complexity: $O(N)$. Although there is a nested
whileloop for expansion, the right boundaryRonly moves forward, and each character comparison either increasesRor finishes the expansion for that center. - Space Complexity: $O(N)$ to store the transformed string and the radii array.
C++ Implementation
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
string solve() {
string s;
if (!(cin >> s)) return "";
// Preprocess the string
string t = "#";
for (char c : s) {
t += c;
t += "#";
}
int n = t.length();
vector<int> p(n, 0);
int center = 0, right = 0;
int maxLen = 0, startIdx = 0;
for (int i = 0; i < n; i++) {
// Use mirroring property
if (i < right) {
p[i] = min(right - i, p[2 * center - i]);
}
// Attempt to expand around i
int left_ptr = i - (p[i] + 1);
int right_ptr = i + (p[i] + 1);
while (left_ptr >= 0 && right_ptr < n && t[left_ptr] == t[right_ptr]) {
p[i]++;
left_ptr--;
right_ptr++;
}
// Update center and right boundary
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
// Track maximum
if (p[i] > maxLen) {
maxLen = p[i];
startIdx = (i - maxLen) / 2;
}
}
return s.substr(startIdx, maxLen);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout << solve() << endl;
return 0;
}