Longest Happy Prefix

Problem (restated)

A happy prefix is a non-empty proper prefix that is also a suffix. Return the longest happy prefix of s, or "".

Intuition

That is the definition of lps[n-1]. Build the LPS array of s and take s[:lps[n-1]].

Approaches

export function longestPrefix(s: string): string {
  const n = s.length;
  if (n === 0) return "";
  const lps = new Array<number>(n).fill(0);
  let length = 0;
  for (let i = 1; i < n; i++) {
    while (length > 0 && s[i] !== s[length]) length = lps[length - 1]!;
    if (s[i] === s[length]) length++;
    lps[i] = length;
  }
  return s.slice(0, lps[n - 1]!);
}

export function longestPrefix(s: string): string {
  const n = s.length;
  if (n === 0) return "";
  const lps = new Array<number>(n).fill(0);
  let length = 0;
  for (let i = 1; i < n; i++) {
    while (length > 0 && s[i] !== s[length]) length = lps[length - 1]!;
    if (s[i] === s[length]) length++;
    lps[i] = length;
  }
  return s.slice(0, lps[n - 1]!);
}

Template connection

Longest happy prefix = LPS of the string. LC 459 uses the same last LPS value as a period.

Reflection

• The happy prefix is the prefix whose length is the last LPS value. 0 means the empty string.
• It has to be proper: the whole string does not count. One character is empty. aaaa answers three a’s.
• The failure table is built from the start. The prefix and the suffix are the same sequence, not a piece taken from the middle.