Problem
Given a string, find the longest palindromic substring in linear time i.e. substring that is also a palindrome. Subsequently, Find all palindromic substrings of a given string
We have already seen simple O(n^2)
solution here - Longest Palindromic Substring, but now lets look at Manacher’s Algorithm, which help us find the solution in linear time.
Solution
Method 1 - Manacher’s Algorithm
Intuition
- Symmetry of Palindromes:
- Palindromes exhibit symmetry: If a substring is a palindrome, there is a central point around which it’s symmetric.
- Preprocessing:
- To handle odd- and even-length palindromes uniformly, we preprocess the string by inserting special characters (e.g.,
'#'
) between every character in the string, including the boundaries. For example:"babad"
becomes"#b#a#b#a#d#"
.
- To handle odd- and even-length palindromes uniformly, we preprocess the string by inserting special characters (e.g.,
- Palindrome Radius:
- For every position in the string, we calculate the radius of the palindrome centred at that position.
- Optimised Expansion:
- Instead of expanding at every character independently, we leverage the symmetry of palindromes and use previously computed results.
Approach
- Preprocessing:
- Transform the input string
s
by inserting special characters:- Original:
"babad"
- Transformed:
"#b#a#b#a#d#"
- Original:
- This ensures all palindromes are odd-length, simplifying calculations.
- Transform the input string
- Initialisation:
- Create an auxiliary array
p
wherep[i]
stores the radius of the palindrome centred at positioni
. - Maintain two key variables:
center
: The centre of the palindrome currently being expanded.right
: The right boundary (exclusive) of this palindrome.
- Create an auxiliary array
- Iterative Expansion:
- For each index
i
in the transformed string:- If
i
falls within the current palindrome (i < right
), mirror the palindrome radius at the symmetric point (mirror = 2*center - i
) to initialisep[i]
. - Expand around
i
outward while the left and right characters match. - Update
center
andright
if the newly expanded palindrome extends beyond the current right boundary.
- If
- For each index
- Post-Processing:
- The longest palindrome in the original string corresponds to the maximum radius in the
p
array.
- The longest palindrome in the original string corresponds to the maximum radius in the
Code
|
|
|
|
Example Walkthrough: "babad"
Preprocessing
- Transformed string:
"#b#a#b#a#d#"
Initialisation
p = [0] * len(transformed_string)
(stores palindrome radii for each character).center = 0
,right = 0
.
Iteration Steps
- For
i = 0
('#'
):- Palindrome radius is
0
(boundary character).
- Palindrome radius is
- For
i = 1
('b'
):- Expand outward (
'#b#'
→ radius = 1 ati
). - Update
center = 1
,right = 2
.
- Expand outward (
- For
i = 2
('#'
):- Palindrome radius is
0
(boundary character).
- Palindrome radius is
- For
i = 3
('a'
):- Expand outward (
'#a#b#a#'
→ radius = 3 ati
). - Update
center = 3
,right = 6
.
- Expand outward (
- For
i = 4
('#'
):- Mirror previous calculations (
p[4] = p[2] = 0
).
- Mirror previous calculations (
- … Continuing Calculation …:
- You eventually compute the radii for all indices:
p = [0, 1, 0, 3, 0, 1, 0, 5, 0, 1, 0, 3, 0, 1, 0]
.
- You eventually compute the radii for all indices:
Post-Processing
- Find the maximum radius in
p
(e.g.,radius = 5
ati = 7
). - Map this back into the original string, removing special characters:
- Longest palindrome is
"bab"
or"aba"
.
- Longest palindrome is
Complexity
- ⏰ Time complexity:
O(n)
. The iterative expansion leverages precomputed results, ensuring linear complexity. - 🧺 Space complexity:
O(n)
. The transformed string and auxiliary arrayp
both consume linear space.