Manacher's Algorithm: Fast and Efficient Palindrome Detection

Note for myself

• add special char just to partition them for expansion e.g. # → #A#B#B#C#
• initialise ⇒ maxRight=0, palindromLengths=[], center=0
• by looping it we check if the current i is within maxRight, if yes, we use a
  • mirror = center*2 - i
  • min(maxRight - i, p[mirror]) for the case when the part of palindrome is not starting from 0
• and every loop just move the maxRight and center when i + p[i] > R ⇒ maxRight = i + p[i], center=i
• case below is looking for the number of palindrome:

   1const countSubstrings = (s) => { // Manacher's algorithm
   2  let modifiedString = '#';
   3  for (let i = 0; i < s.length; i++) {
   4    modifiedString += s[i] + '#';
   5  }
   6
   7  const n = modifiedString.length;
   8  const P = new Array(n).fill(0);
   9  let center = 0, right = 0;
  10  let count = 0;
  11
  12  for (let i = 0; i < n; i++) {
  13    if (i <= right) {
  14      const mirror = 2 * center - i;
  15      P[i] = Math.min(right - i, P[mirror]);
  16    }
  17
  18    let leftIndex = i - (1 + P[i]);
  19    let rightIndex = i + (1 + P[i]);
  20
  21    while (leftIndex >= 0 && rightIndex < n && modifiedString[leftIndex] === modifiedString[rightIndex]) {
  22      P[i]++;
  23      leftIndex--;
  24      rightIndex++;
  25    }
  26
  27    if (i + P[i] > right) {
  28      center = i;
  29      right = i + P[i];
  30    }
  31
  32    count += Math.ceil(P[i] / 2);
  33  }
  34
  35  return count;
  36};
  

rewind please its hard to actually memorise - do it again!

What is Manacher’s Algorithm?

Manacher’s algorithm is an efficient algorithm used to find the longest palindromic substring in a given string. It was invented by Gustav Manacher in 1975. The algorithm works by using the properties of palindromic substrings to avoid unnecessary comparisons, thereby reducing the overall time complexity.

Overall, Manacher’s algorithm is a very elegant and efficient solution to the problem of finding the longest palindromic substring in a given string.

The algorithm uses two key ideas:

1. Symmetry property: A palindrome has a symmetry around its center. If we already know the palindrome of a center, we can use it to avoid checking characters that cannot be part of a longer palindrome.
2. Dynamic Programming: We can use previous calculations to compute new ones.

The Manacher’s algorithm has a time complexity of O(n), where n is the length of the string, which makes it very efficient.

Here’s how the Manacher algorithm works:

1. Preprocess the input string s by inserting a special character, such as ‘#’, between each pair of characters to make the string odd-length. For example, the string “abba” would become “#a#b#b#a#”.

2. Initialise two arrays:

   1. P, where P[i] stores the length of the longest palindromic substring centered at i, and
   2. C, where C[i] stores the center of the longest palindromic substring found so far.

3. Set a variable called maxRight to 0, which represents the rightmost boundary of the longest palindromic substring found so far, and set center to 0, which represents its center.

4. Iterate through the string s from left to right, and for each character i, do the following:

   a. If i is within the current palindromic substring (i.e., i <= maxRight), set P[i] to min(P[2 * center - i], maxRight - i), which means the palindrome centered at i is a reflection of the palindrome centered at center.

   b. Expand the palindrome centered at i by comparing characters s[i - P[i] - 1] and s[i + P[i] + 1]. If they are equal, increase P[i] by 1.

   c. If the expanded palindrome centered at i extends beyond maxRight, update maxRight and center accordingly.

5. Find the maximum value in the P array, and its corresponding center index. The longest palindromic substring is then the substring centered at this index, with length P[center] - 1.

For myself

My workaround:

References

• YouTube - LeetCode Solution - 5.0 Longest Palindromic Substring | Manacher Algorithm 100% Beat