Problem 35.4 · Advanced String AlgorithmsHard

Longest Happy Prefix

PatternString Matching (KMP, Z, Rolling Hash)

What it teaches: The answer is exactly lps[n − 1].

Practise it on judges as “Longest Happy Prefix”.

In plain words

Find the longest piece that a word both starts with and ends with, without using the whole word. For "ababab" the start "abab" is also the end. The KMP table (lps) records exactly this for every prefix of the word, so its last entry is the answer's length.

Return the longest happy prefix, or "". Example: s = "ababab" → "abab".

The problem

A happy prefix is a non-empty prefix that is also a suffix (excluding the whole string). Return the longest one, or "".

Example 1

Input: s = "ababab"
Output: "abab"

Constraints

1 ≤ n ≤ 10⁵

Pattern clues in the wording

→ Prefix equal to suffix

These clues point to String Matching (KMP, Z, Rolling Hash): Find a pattern inside a text in linear time by reusing what earlier comparisons already proved, or by comparing hashes instead of characters.

Stuck? Take one hint at a time

Solution · starter

class Solution {
    public String longestPrefix(String s) {
        return "";
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	s = "level"	"l"
2	s = "ababab"	"abab"
3	s = "a"	""

From slow to fast

Approaches

1. KMP failure table · O(n)

KMP failure table

Time O(n) Space O(n)

Return s.substring(0, lps[n − 1]).

▶ Dry run: Building the lps tables = "ababab"

Step 1/4lps[0] is always 0. At i = 1, 'b' doesn't match s[0] = 'a', and len is 0, so lps[1] = 0.

Approach 1

class Solution {
    public String longestPrefix(String s) {
        int n = s.length();
        int[] lps = new int[n];
        for (int i = 1, len = 0; i < n; ) {
            if (s.charAt(i) == s.charAt(len)) lps[i++] = ++len;
            else if (len > 0) len = lps[len - 1];
            else lps[i++] = 0;
        }
        return s.substring(0, lps[n - 1]);
    }
}

Verdict: Direct.

Before you submit

Edge cases and common mistakes

Test these inputs

Single character ("")
Overlapping prefix and suffix

Mistakes people make

Comparing every prefix with the suffix directly (O(n²)).

Interview

Follow-up questions

How would you do it with hashing?

Command Palette

The problem

Approaches

KMP failure table

Edge cases and common mistakes

Follow-up questions