Longest Happy Prefix

Hard
658.

Longest Happy Prefix

Longest Happy Prefix is a hard coding problem on strings, rolling hash and KMP Algorithm, asked in Amazon, Google and Microsoft interviews.

A happy prefix is a non-empty prefix that is also a suffix, but not the whole string.

Given s, return its longest happy prefix, or the empty string if it has none.

Example 1

Input
s = "level"
Output
l
Explanation
Prefixes that are also suffixes: "l". "le" is not a suffix.

Example 2

Input
s = "ababab"
Output
abab
Explanation
"abab" is both a prefix and a suffix; "ababab" itself does not count.

Example 3

Input
s = "codekairo"
Output
Explanation
No proper prefix is also a suffix.

Constraints

  • 1 <= s.length <= 100000
  • s consists of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var longestPrefix = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Happy Prefix — Solution in Python, Java & C++

Longest Happy Prefix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Longest Happy Prefix is a hard coding problem on strings, rolling hash and KMP Algorithm, asked in Amazon, Google and Microsoft interviews.

Problem statement

A happy prefix is a non-empty prefix that is also a suffix, but not the whole string.

Given s, return its longest happy prefix, or the empty string if it has none.

Example 1

Input: s = "level"
Output: l
Explanation: Prefixes that are also suffixes: "l". "le" is not a suffix.

Example 2

Input: s = "ababab"
Output: abab
Explanation: "abab" is both a prefix and a suffix; "ababab" itself does not count.

Example 3

Input: s = "codekairo"
Output: 
Explanation: No proper prefix is also a suffix.

Constraints

  • 1 <= s.length <= 100000
  • s consists of lowercase English letters.

Hints for Longest Happy Prefix

  1. Hint 1

    This is exactly the value KMP's failure function computes at the last index.

  2. Hint 2

    fail[i] is the length of the longest proper prefix of s[0..i] that is also a suffix of it.

  3. Hint 3

    Build fail left to right, falling back through fail[j-1] on a mismatch.

How to solve Longest Happy Prefix

The longest happy prefix is by definition the last value of KMP's prefix function, so the whole problem is one failure-function build.

Approach

  1. Set fail[0] = 0.
  2. For each i from 1, start j = fail[i-1] and, while j > 0 and s[i] != s[j], fall back to j = fail[j-1].
  3. If s[i] == s[j], increment j; store fail[i] = j.
  4. Return the first fail[n-1] characters of s.

Why it works

The fallback chain j, fail[j-1], fail[fail[j-1]-1], … enumerates every border of the current prefix in decreasing length, so the first one that can be extended by s[i] gives the longest border of the prefix ending at i. Because fail never counts the whole string, the result is automatically proper.

Complexity

  • Time — O(n) — the fallback chain is amortised constant
  • Space — O(n)

Pitfalls

  • Comparing every prefix with the matching suffix directly is O(n²) and times out.
  • Returning s itself when the string is uniform — the prefix must be proper, which fail guarantees.
  • A rolling hash also works but needs a double hash to be safe against collisions at this input size.

Reference solution

Python

def longestPrefix(s: str) -> str:
    n = len(s)
    fail = [0] * n
    for i in range(1, n):
        j = fail[i - 1]
        while j > 0 and s[i] != s[j]:
            j = fail[j - 1]
        if s[i] == s[j]:
            j += 1
        fail[i] = j
    return s[:fail[n - 1]]

Java

public static String longestPrefix(String s) {
    int n = s.length();
    int[] fail = new int[n];
    for (int i = 1; i < n; i++) {
        int j = fail[i - 1];
        while (j > 0 && s.charAt(i) != s.charAt(j)) j = fail[j - 1];
        if (s.charAt(i) == s.charAt(j)) j++;
        fail[i] = j;
    }
    return s.substring(0, fail[n - 1]);
}

C++

string longestPrefix(string s) {
    int n = (int) s.size();
    vector<int> fail(n, 0);
    for (int i = 1; i < n; i++) {
        int j = fail[i - 1];
        while (j > 0 && s[i] != s[j]) j = fail[j - 1];
        if (s[i] == s[j]) j++;
        fail[i] = j;
    }
    return s.substr(0, fail[n - 1]);
}

JavaScript

var longestPrefix = function(s) {
    var n = s.length;
    var fail = [];
    for (var t = 0; t < n; t++) fail.push(0);
    for (var i = 1; i < n; i++) {
        var j = fail[i - 1];
        while (j > 0 && s.charAt(i) !== s.charAt(j)) j = fail[j - 1];
        if (s.charAt(i) === s.charAt(j)) j++;
        fail[i] = j;
    }
    return s.substr(0, fail[n - 1]);
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings