Shortest Palindrome

Problem (restated)

Add the shortest prefix to s so the result is a palindrome. You may only add characters in front.

Intuition

You want the longest prefix of s that is already a palindrome, then prepend the reverse of the leftover suffix. That longest palindromic prefix is lps[-1] of s + '#' + reverse(s): the # blocks wrap-around, so the LPS at the end is how much of s matches a suffix of the reverse — a palindromic prefix.

Approaches

function buildLps(pattern: string): number[] {
  const lps = new Array<number>(pattern.length).fill(0);
  let length = 0;
  for (let i = 1; i < pattern.length; i++) {
    while (length > 0 && pattern[i] !== pattern[length]) length = lps[length - 1]!;
    if (pattern[i] === pattern[length]) length++;
    lps[i] = length;
  }
  return lps;
}

export function shortestPalindrome(s: string): string {
  if (!s) return s;
  const rev = [...s].reverse().join("");
  const lps = buildLps(`${s}#${rev}`);
  return rev.slice(0, s.length - lps[lps.length - 1]!) + s;
}

function buildLps(pattern: string): number[] {
  const lps = new Array<number>(pattern.length).fill(0);
  let length = 0;
  for (let i = 1; i < pattern.length; i++) {
    while (length > 0 && pattern[i] !== pattern[length]) length = lps[length - 1]!;
    if (pattern[i] === pattern[length]) length++;
    lps[i] = length;
  }
  return lps;
}

export function shortestPalindrome(s: string): string {
  if (!s) return s;
  const rev = [...s].reverse().join("");
  const lps = buildLps(`${s}#${rev}`);
  return rev.slice(0, s.length - lps[lps.length - 1]!) + s;
}

Template connection

Shortest palindrome via LPS of pattern + reverse. Same LPS builder as LC 28.

Reflection

• Build LPS of s + '#' + reverse(s). That last value is the longest palindromic prefix of s. Prepend reverse(s)[0 : n - lps[-1]].
• The # stops the prefix and the suffix from running into each other. If s is already a palindrome, the prepended piece is empty.
• One character is itself. Without the separator, LPS grows across the join.