Longest Happy Prefix Hard 0 attempts
LeetCode ↗

Longest Happy Prefix

Hard StringHash Table LeetCode

Call a non-empty prefix of a string a happy prefix if that same sequence of characters also shows up as a suffix of the string, as long as it isn't the whole string itself. Given a string s, find its longest happy prefix, or return an empty string if none exists.

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

Input Format
Implement longestPrefix(s). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
s = "level"
Output
"l"

Example 2

Input
s = "ababab"
Output
"abab"
Constraints
  • 1 <= s.length <= 10^5
  • s contains only lowercase English letters
Test Cases (2)
Case 1
Args: ["level"] Expected: "l"
Case 2
Args: ["ababab"] Expected: "abab"
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.

javascript
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