1392. Longest Happy Prefix

1392

HardTrie and Advanced String SearchKMP prefix functionLongest proper prefix that is also a suffix

Longest Happy Prefix

A happy prefix of a string is a non-empty prefix that is also a suffix, but not the whole string itself. Given a string s, return its longest happy prefix, or the empty string if none exists.

Open official problem prompt ↗

In plain English

Find the longest string that is simultaneously a proper prefix and a proper suffix of s.

Picture it like this

Like folding a strip of paper so its left edge overlaps its right edge as much as possible without covering the whole strip; the overlap length is the answer.

Example

Input: s = "level"
Output: "l"
Why: "l" is both the first and last character of "level", and no longer prefix (le, lev, leve) also appears as a suffix.

Constraints

1 <= s.length <= 10^5s contains only lowercase English letters

Pattern lesson

See the pattern, then code

Longest proper prefix that is also a suffix

↗

Trie and Advanced String Search

Repeated prefix lookup, autocomplete, dictionary search, or many-word matching.. The KMP prefix function pi[i] already stores, for each position, the length of the longest proper prefix of s[0..i] that is also its suffix, so pi[n-1] is the answer length for the whole string.

New words, made simpleKnow these before the algorithm

Proper prefix/suffix: A prefix or suffix that is not the entire string.
Prefix function (pi): pi[i] = length of the longest proper prefix of s[0..i] that is also a suffix of it.
Failure link: The fallback pi[k-1] used to shorten the match after a mismatch instead of restarting from scratch.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Compare all prefix/suffix pairs

Each comparison can cost O(n) and there are O(n) lengths, too slow for n up to 10^5.

For each length L from n-1 down to 1, check whether s[:L] equals s[n-L:] and return the first hit.

Time O(n^2)Space O(1)

Best choiceKMP prefix function

Linear time, exactly the value the failure function was designed to compute.

Build pi in one pass with amortized O(1) work per character using failure links, then read pi[n-1].

Time O(n)Space O(n)

The rule we keep true

Invariant

After processing index i, pi[i] equals the length of the longest proper prefix of s[0..i] that is also a suffix of s[0..i], and k always equals pi[i-1] going into iteration i.

Why this is correct

Reasoning

The prefix function extends the current match when characters agree and otherwise follows failure links to the next-longest candidate border, never re-examining a character more than a bounded number of times. Its last entry describes the whole string, giving the longest border, which is precisely the longest happy prefix.

The algorithm in three movesSay these aloud before coding

1Compute the prefix-function array pi over s

pi = [0,0,0,0,1]

2Track a matched length k, extending it when characters agree

final k = pi[4] = 1

3On mismatch, fall back to pi[k-1] until a match or k hits 0

answer = s[:1] = 'l'

4Return the prefix of s whose length is pi[n-1]

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readcompare s[1]='e' with s[0]='l'

2 · AskExtend the match?

3 · Update statek=0, pi=[0,0,_,_,_]

4 · ResultNo match, pi[1]=0

Key takeaway

For 'level' the matched length reaches 1 only at the last character, where the trailing 'l' matches the leading 'l'.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-5Initialize
pi starts all zeros and the matched length k starts at 0; pi[0] is always 0 since a single character has no proper border.
2
Lines 6-8Fallback on mismatch
While the next character disagrees, jump k back to pi[k-1] to try the next shorter border rather than restart.
3
Lines 9-11Extend and record
When s[i] matches s[k], grow k by one and store it as pi[i].
4
Lines 12Read the answer
pi[-1] is the longest border length for the whole string, so s[:pi[-1]] is the longest happy prefix.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Single-character string returns "" (no proper border)
No prefix equals any suffix, e.g. "abcd" returns ""
The border overlaps itself, e.g. "aaaa" returns "aaa"
Answer longer than half the string, handled naturally by the failure links

Common beginner mistakes

Returning the whole string; the border must be proper (strictly shorter than s)
Restarting the scan from 0 on a mismatch instead of following pi[k-1], which reintroduces O(n^2) behavior
Off-by-one when indexing pi[k-1] versus pi[k]
Trying naive prefix/suffix comparison and timing out at n = 10^5

Check your understanding

Why is pi[n-1] exactly the length of the longest happy prefix?

Longest Happy Prefix

Longest Happy Prefix

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Trie and Advanced String Search