An optimal linear-time $O(N)$ algorithm for finding the minimum number of characters required to insert at the beginning of a string to convert it into a palindrome.

Problem Statement

Given a string s, find the minimum number of characters that must be added in front of s to make the entire string a palindrome.

Optimal Approach: Knuth-Morris-Pratt (KMP) LPS Array

The naive approach checks all substrings starting from the end, taking $O(N^2)$ time. We can achieve optimal $O(N)$ time complexity using the Longest Prefix Suffix (LPS) preprocessing array from the KMP string matching algorithm.

1. Construct a temporary string concat = s + '$' + reverse(s).
2. Compute the LPS array of concat.
3. The last value LPS[concat.length - 1] represents the length of the longest palindromic prefix of s.
4. The answer is simply s.length - LPS[concat.length - 1].

TypeScript Implementation

function minCharactersToMakePalindrome(s: string): number {
  const rev = s.split('').reverse().join('');
  const combined = s + '#' + rev;
  const n = combined.length;
  const lps = new Array(n).fill(0);

  let len = 0;
  let i = 1;
  while (i < n) {
    if (combined[i] === combined[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }

  return s.length - lps[n - 1];
}

Complexity Analysis

• Time Complexity: $O(N)$ linear time to compute the KMP prefix table.
• Space Complexity: $O(N)$ memory to store the LPS array and reversed string.