Longest Happy Prefix — Hard Problem & Solution

A happy prefix is a non-empty prefix that is also a suffix, but not the whole string.

Difficulty: Hard
Topics: Strings, Rolling Hash, KMP Algorithm
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A happy prefix is a non-empty prefix that is also a suffix, but not the whole string.

Given s, return its longest happy prefix, or the empty string if it has none.

Example 1

Input: s = "level"
Output: l
Explanation: Prefixes that are also suffixes: "l". "le" is not a suffix.

Example 2

Input: s = "ababab"
Output: abab
Explanation: "abab" is both a prefix and a suffix; "ababab" itself does not count.

Example 3

Input: s = "codekairo"
Output: 
Explanation: No proper prefix is also a suffix.

Constraints

1 <= s.length <= 100000
s consists of lowercase English letters.

How to solve Longest Happy Prefix

The longest happy prefix is by definition the last value of KMP's prefix function, so the whole problem is one failure-function build.

Approach

Set fail[0] = 0.
For each i from 1, start j = fail[i-1] and, while j > 0 and s[i] != s[j], fall back to j = fail[j-1].
If s[i] == s[j], increment j; store fail[i] = j.
Return the first fail[n-1] characters of s.

Why it works

The fallback chain j, fail[j-1], fail[fail[j-1]-1], … enumerates every border of the current prefix in decreasing length, so the first one that can be extended by s[i] gives the longest border of the prefix ending at i. Because fail never counts the whole string, the result is automatically proper.

Complexity

Time — O(n) — the fallback chain is amortised constant
Space — O(n)

Pitfalls

Comparing every prefix with the matching suffix directly is O(n²) and times out.
Returning s itself when the string is uniform — the prefix must be proper, which fail guarantees.
A rolling hash also works but needs a double hash to be safe against collisions at this input size.

Reference solution

Python

def longestPrefix(s: str) -> str:
    n = len(s)
    fail = [0] * n
    for i in range(1, n):
        j = fail[i - 1]
        while j > 0 and s[i] != s[j]:
            j = fail[j - 1]
        if s[i] == s[j]:
            j += 1
        fail[i] = j
    return s[:fail[n - 1]]

JavaScript

var longestPrefix = function(s) {
    var n = s.length;
    var fail = [];
    for (var t = 0; t < n; t++) fail.push(0);
    for (var i = 1; i < n; i++) {
        var j = fail[i - 1];
        while (j > 0 && s.charAt(i) !== s.charAt(j)) j = fail[j - 1];
        if (s.charAt(i) === s.charAt(j)) j++;
        fail[i] = j;
    }
    return s.substr(0, fail[n - 1]);
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue