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.

Examples

Example 1:

1
2
3

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Solution

Method 1 - Manacher’s Algorithm

Intuition

  1. Symmetry of Palindromes:
    • Palindromes exhibit symmetry: If a substring is a palindrome, there is a central point around which it’s symmetric.
  2. 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#".
  3. Palindrome Radius:
    • For every position in the string, we calculate the radius of the palindrome centred at that position.
  4. Optimised Expansion:
    • Instead of expanding at every character independently, we leverage the symmetry of palindromes and use previously computed results.

Approach

  1. Preprocessing:
    • Transform the input string s by inserting special characters:
      • Original: "babad"
      • Transformed: "#b#a#b#a#d#"
    • This ensures all palindromes are odd-length, simplifying calculations.
  2. Initialisation:
    • Create an auxiliary array p where p[i] stores the radius of the palindrome centred at position i.
    • Maintain two key variables:
      • center: The centre of the palindrome currently being expanded.
      • right: The right boundary (exclusive) of this palindrome.
  3. 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 initialise p[i].
      • Expand around i outward while the left and right characters match.
      • Update center and right if the newly expanded palindrome extends beyond the current right boundary.
  4. Post-Processing:
    • The longest palindrome in the original string corresponds to the maximum radius in the p array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
    public String longestPalindrome(String s) {
        // Step 1: Preprocess the string
        StringBuilder sb = new StringBuilder();
        sb.append("#"); // Add boundary character to simplify palindrome handling
        for (char c : s.toCharArray()) {
            sb.append(c);
            sb.append("#");
        }
        String transformed = sb.toString();
        int n = transformed.length(); 
        
        // Step 2: Initialise auxiliary array
        int[] p = new int[n]; // Array to track palindrome radii
        int center = 0, right = 0; // Current center and right boundary of palindrome

        // Step 3: Expand around each character
        for (int i = 0; i < n; i++) {
            int mirror = 2 * center - i; // Mirrored index for `i`
            if (i < right) {
                p[i] = Math.min(p[mirror], right - i); // Initialise radius
            }
            
            // Try to expand the palindrome centered at `i`
            int a = i + p[i] + 1;
            int b = i - p[i] - 1;
            while (a < n && b >= 0 && transformed.charAt(a) == transformed.charAt(b)) {
                p[i]++;
                a++;
                b--;
            }
            
            // Update center and right boundary if palindrome expands beyond right
            if (i + p[i] > right) {
                center = i;
                right = i + p[i];
            }
        }

        // Step 4: Find the longest palindrome
        int maxLen = 0, start = 0;
        for (int i = 0; i < n; i++) {
            if (p[i] > maxLen) {
                maxLen = p[i];
                start = (i - maxLen) / 2; // Map back to original string
            }
        }

        return s.substring(start, start + maxLen);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # Step 1: Preprocess the string
        transformed = "#".join(f"#{s}#")
        n = len(transformed)
        
        # Step 2: Initialise auxiliary array
        p = [0] * n  # Array to track palindrome radii
        center = 0   # Current center of the palindrome
        right = 0    # Right boundary of the palindrome

        # Step 3: Expand around each character
        for i in range(n):
            mirror = 2 * center - i  # Mirrored index for `i`
            if i < right:
                p[i] = min(p[mirror], right - i)  # Initialise radius

            # Try to expand the palindrome centered at `i`
            a, b = i + p[i] + 1, i - p[i] - 1
            while a < n and b >= 0 and transformed[a] == transformed[b]:
                p[i] += 1
                a += 1
                b -= 1

            # Update center and right boundary if palindrome expands beyond right
            if i + p[i] > right:
                center = i
                right = i + p[i]

        # Step 4: Find the longest palindrome
        max_len, center_index = max((p[i], i) for i in range(n))
        start = (center_index - max_len) // 2  # Map back to original string

        return s[start:start + max_len]

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
  1. For i = 0 ('#'):
    • Palindrome radius is 0 (boundary character).
  2. For i = 1 ('b'):
    • Expand outward ('#b#' → radius = 1 at i).
    • Update center = 1, right = 2.
  3. For i = 2 ('#'):
    • Palindrome radius is 0 (boundary character).
  4. For i = 3 ('a'):
    • Expand outward ('#a#b#a#' → radius = 3 at i).
    • Update center = 3, right = 6.
  5. For i = 4 ('#'):
    • Mirror previous calculations (p[4] = p[2] = 0).
  6. … 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].
Post-Processing
  • Find the maximum radius in p (e.g., radius = 5 at i = 7).
  • Map this back into the original string, removing special characters:
    • Longest palindrome is "bab" or "aba".

Complexity

  • ⏰ Time complexity: O(n). The iterative expansion leverages precomputed results, ensuring linear complexity.
  • 🧺 Space complexity: O(n). The transformed string and auxiliary array p both consume linear space.