Longest Happy Prefix Hard 0 attempts
LeetCode ↗

Longest Happy Prefix

Hard StringHash Table LeetCode

A happy prefix is a non-empty prefix of a string that is also a suffix (excluding the entire string itself). Given a string s, return the longest happy prefix. If no such prefix exists, return an empty string.

Example 1:

Input: s = "level"
Output: "l"
Explanation: "l" is both a prefix and suffix. "le" is a prefix but not a suffix.

Example 2:

Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the longest string that is both a prefix and suffix.

Example 3:

Input: s = "a"
Output: ""

Edge cases: Single character strings always return "". Strings where all characters are the same (e.g., "aaaa" → "aaa").

Sample Input
s = "level"
Sample Output
"l"
Constraints
  • 1 <= s.length <= 10^5
  • s contains only lowercase English letters
Test Cases
Case 1
Args: ["level"] Expected: "l"
Topics
StringHash Table

Approach: KMP Failure Function

This is directly solved by the KMP algorithm's LPS (Longest Proper Prefix which is also Suffix) array. Build the LPS array for the entire string — the value at the last index gives the length of the longest happy prefix.

function longestPrefix(s) {
  const n = s.length;
  const lps = new Array(n).fill(0);
  let len = 0;
  let i = 1;

  while (i < n) {
    if (s[i] === s[len]) {
      len++;
      lps[i] = len;
      i++;
    } else if (len > 0) {
      len = lps[len - 1];
    } else {
      i++;
    }
  }
  return s.substring(0, lps[n - 1]);
}

Time Complexity: O(n)

Space Complexity: O(n) for the LPS array

Saved in this browser only. Private to you.

JavaScript