AlgoMaster Logo

Longest Happy Prefix

hardFrequencyUpdated September 21, 2026

Understanding the Problem

We need to find the longest proper prefix of a string that is also a suffix of that same string. "Proper" means we can't use the entire string itself, so for "abc", valid prefixes are "a" and "ab", and valid suffixes are "c" and "bc". None match, so the answer is empty.

Example 2 shows that the prefix and suffix can overlap. In "ababab", the prefix "abab" (characters 0-3) and the suffix "abab" (characters 2-5) share characters 2 and 3. That is allowed. We are not looking for non-overlapping matches, only a prefix that equals a suffix.

This is the same quantity the KMP algorithm's LPS (Longest Prefix Suffix) array computes at each position. The last entry of the LPS array is the length of the longest proper prefix that is also a suffix of the entire string, which is exactly what this problem asks for.

Key Constraints:

  • 1 <= s.length <= 10^5: The string can be up to 100,000 characters. An O(n^2) brute force would mean up to 10^10 character comparisons in the worst case, which is too slow. We need O(n) or O(n log n).
  • s contains only lowercase English letters, 26-character alphabet, which is relevant for rolling hash approaches where we need a base and modulus.
  • s.length >= 1: We need to handle single-character strings, where the answer is always empty (no proper prefix exists).

Approach 1: Brute Force

Intuition

Try every possible prefix length from longest to shortest, and for each one, check whether the prefix equals the corresponding suffix. Because we check from longest to shortest, the first match we find is the answer.

For a string of length n, the valid prefix lengths range from n-1 (the longest proper prefix) down to 1. For each candidate length k, we compare the first k characters with the last k characters. If they're identical, that's our answer.

Algorithm

  1. Let n be the length of s.
  2. For each candidate length k from n - 1 down to 1:
    • Compare s[0..k-1] with s[n-k..n-1].
    • If they match, return s[0..k-1].
  3. If no match is found, return an empty string.

Visualization and Code

Loading animation...

With n up to 100,000, this is too slow. The next approach replaces the character-by-character comparison with an O(1) hash comparison.

Approach 2: Rolling Hash (Rabin-Karp)

Intuition

A polynomial hash maps a string to a single number, a fingerprint. If two strings have different fingerprints they are different; if the fingerprints match they are equal with high probability. We maintain two running hashes as we scan: one for the prefix growing from the left, one for the suffix growing from the right. At each length k, if the two hashes match, length k is a candidate happy prefix.

The reason this beats brute force is that each extension updates both hashes in O(1) arithmetic, so the full scan is O(n) instead of O(n^2).

Algorithm

  1. Initialize prefixHash = 0, suffixHash = 0, power = 1, and longestLen = 0.
  2. Choose a prime base (e.g., 31) and a large prime modulus (e.g., 10^9 + 7).
  3. For each index i from 0 to n - 2:
    • Update the prefix hash: prefixHash = prefixHash * base + s[i].
    • Update the suffix hash: suffixHash = s[n - 1 - i] * power + suffixHash.
    • Update power = power * base.
    • If prefixHash == suffixHash, set longestLen = i + 1.
  4. Return s[0..longestLen-1].

Visualization and Code

Loading animation...

Rolling hash gives O(n) time but carries a small chance of a hash collision producing a wrong answer. The next approach, based on KMP, is O(n) and deterministic with no collision risk.

Approach 3: KMP (LPS Array)

Intuition

The KMP algorithm's preprocessing step builds an LPS (Longest Prefix Suffix) array, where lps[i] stores the length of the longest proper prefix of s[0..i] that is also a suffix of s[0..i]. The answer to this problem is lps[n - 1], the LPS value for the whole string. If lps[n - 1] = k, the first k characters of s equal the last k characters.

The LPS array is built with a single pointer len that tracks how much of the current prefix-suffix has matched. When the next character extends the match, len increases by one. On a mismatch, instead of restarting, len falls back to lps[len - 1], the length of the next-shorter prefix that is also a suffix of what has matched so far. That fallback is what keeps the algorithm linear.

Algorithm

  1. Create an array lps of size n, initialized to all zeros.
  2. Set len = 0 (length of the current matched prefix-suffix) and i = 1.
  3. While i < n:
    • If s[i] == s[len], set lps[i] = len + 1, increment both len and i.
    • Else if len > 0, fall back: set len = lps[len - 1] (don't increment i).
    • Else, set lps[i] = 0 and increment i.
  4. Return s[0..lps[n-1]-1].

Visualization and Code

Loading animation...