Longest Happy Prefix (LeetCode 1392)

The problem

A happy prefix of a string s is a non-empty prefix that is also a suffix, and is not the whole string. Return the longest happy prefix of s, or "" if there is none.

Input:  s = "level"
Output: "l"

"l" is both the first and last letter. Longer candidates fail: "le" vs "el", "lev" vs "vel", "leve" vs "evel".

How to think about it

Start with brute force. Try each length L from n − 1 down to 1, and check s[:L] == s[-L:]. Each check is O(n), so this is O(n²). With n = 10⁵ that’s too slow on strings like "aaaa…ab".

The key insight: this is the definition of the KMP prefix function. The prefix function lps[i] is the length of the longest proper prefix of s[:i+1] that is also a suffix of it, called its longest border. The happy prefix is the longest border of the whole string, which is lps[n - 1]. One linear pass builds the table, and you read off the last entry.

How the table is built in O(n). Keep k as the length of the current border. For the next character, if s[i] == s[k], the border grows to k + 1. If not, fall back to the next shorter border, lps[k - 1], and try again. The borders of a border are borders too, so you never miss a candidate. k rises at most once per character, so the total number of fallbacks is at most n.

Which pattern is this? The KMP prefix function in its purest form. The tell is “prefix that is also a suffix”. A rolling hash comparing prefix and suffix hashes also works in O(n), but risks collisions.

Approach

1. Create lps of zeros with length n, and k = 0.
2. For i from 1 to n − 1:
   1. While k > 0 and s[i] != s[k], set k = lps[k - 1].
   2. If s[i] == s[k], add one to k.
   3. Store lps[i] = k.
3. Return s[:lps[-1]].

Solution

def longestPrefix(s):
    lps = [0] * len(s); k = 0
    for i in range(1, len(s)):
        while k and s[i] != s[k]:
            k = lps[k - 1]                 # try the next shorter border
        if s[i] == s[k]:
            k += 1                         # border grows by one
        lps[i] = k
    return s[:lps[-1]]                     # longest border of the whole string
# longestPrefix("level") -> "l"

Dry run

On s = "level":

lps[-1] = 1, so the answer is s[:1] = "l". On "ababab" the code builds lps = [0, 0, 1, 2, 3, 4] and returns "abab": borders may overlap.

Complexity

• Time: O(n). Each character advances k at most once, and every fallback lowers k, so the inner while runs at most n times in total.
• Space: O(n). For the lps table.

Edge cases and pitfalls

• Single character returns "": a happy prefix can’t be the whole string, and lps[0] is always 0.
• No border at all ("abc") returns "".
• Overlapping borders are allowed. "aaaa" returns "aaa".
• Using if instead of while for the fallback misses shorter borders and gives wrong values.
• Starting the loop at i = 0 compares s[0] with itself and sets lps[0] = 1, which is wrong; a border must be proper.

Related problems

• Shortest Palindrome (LeetCode 214): the same lps[-1] read off a joined string.
• Repeated Substring Pattern (LeetCode 459): n - lps[-1] gives the string’s period.
• Find the Index of the First Occurrence in a String (LeetCode 28): the prefix function used for full KMP search.