AlgoViz
HomeStrings

Longest happy prefix

Hard

The last entry of the LPS array

Problem

Return the longest proper prefix of a string that is also a suffix (a 'happy prefix').

In simple words

The longest prefix that is also a suffix — read it straight off the last LPS value.

The idea

A happy prefix is a proper prefix that is also a suffix, which is exactly what the LPS array measures. Build the LPS for the whole string and read the final value — that length is the answer.

The trick

  • Answer length = lps[n-1]; the string itself does not count as a proper prefix.
  • O(n) time and space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

0
0

Step 1 of 2. Here's the example — level Values: 0.

1/2
Optimal
timeO(n)spaceO(n)
1build lps array2return s[0 .. lps[n-1]-1]

Input

array
[0]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

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

Example 2

Input:
s = "ababab"
Output:
"abab"
Explanation:
"abab" is the longest happy prefix.

Example 3

Input:
s = "abcd"
Output:
""
Explanation:
No non-trivial match → empty.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.