☕ DSA Java Articles

Topics › Strings › Hard String Problems

Longest happy prefix

Hard TUF ID 978 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A happy prefix of a string is a non-empty prefix that is also a suffix, excluding the string itself. Given s, return its longest happy prefix, or "" if there is none. The prefix and the suffix are allowed to overlap.

Constraints: 1 ≤ n ≤ 10^5 (the Java file also accepts the empty string and returns ""), s consists of lowercase English letters.

Example 1

s = "level"
answer = "l"         // "le" vs "el", "lev" vs "vel", "leve" vs "evel" all differ

Example 2

s = "ababab"
answer = "abab"      // prefix s[0..4) and suffix s[2..6) overlap in "ab"

Example 3

s = "abc"
answer = ""          // no proper prefix equals a suffix of the same length

In KMP terminology a happy prefix is a border, and the question asks for the longest border of the whole string.

Approach 1: Brute force

Intuition. There are only n - 1 candidate lengths. Try them from the longest down and return the first length len for which the prefix s[0..len) equals the suffix s[n-len..n). Trying longest first means the first success is the answer.

Algorithm.

  1. For len = n - 1 down to 1: if s[0..len) equals s[n-len..n), return s[0..len).
  2. Return "".
static String bruteForce(String s) {
    int n = s.length();
    for (int len = n - 1; len >= 1; len--) {
        if (s.regionMatches(0, s, n - len, len)) return s.substring(0, len);
    }
    return "";
}

Complexity. Time O(n^2): up to n lengths, each compared in up to len steps. On "aaa...ab" every comparison runs almost to the end before hitting the b, giving about n^2 / 2 steps, roughly 5 · 10^9 for n = 10^5. Space O(1) besides the returned string.

Approach 2: Better, rolling hashes

Intuition. The brute force spends O(len) per candidate only to compare two strings. With polynomial prefix hashes, the hash of any substring is available in O(1), so each candidate can be rejected in constant time. Only when the hashes agree do we compare characters, to rule out a collision.

With h[i] the hash of s[0..i) and pw[k] = B^k, the hash of the suffix s[n-len..n) is h[n] - h[n-len]·B^len (mod M), and the hash of the prefix is simply h[len]. The suffix formula follows from Horner’s rule: the hash of the whole string equals the hash of s[0..n-len) shifted left by len base-B digits, plus the hash of the last len characters. Subtracting the shifted part leaves the suffix.

Algorithm.

  1. Build h and pw in one pass.
  2. For len = n - 1 down to 1: compute the suffix hash; if it equals h[len] and the strings really match, return s[0..len).
  3. Return "".
static String better(String s) {
    final long MOD = 1_000_000_007L, BASE = 131;
    int n = s.length();
    long[] h = new long[n + 1], pw = new long[n + 1];  // h[i] = hash of s[0..i), pw[i] = BASE^i
    pw[0] = 1;
    for (int i = 0; i < n; i++) {
        h[i + 1] = (h[i] * BASE + s.charAt(i)) % MOD;
        pw[i + 1] = pw[i] * BASE % MOD;
    }
    for (int len = n - 1; len >= 1; len--) {
        long suffix = ((h[n] - h[n - len] * pw[len]) % MOD + MOD) % MOD;   // hash of s[n-len..n)
        if (h[len] == suffix && s.regionMatches(0, s, n - len, len)) return s.substring(0, len);
    }
    return "";
}

Complexity. Time O(n) expected: one linear pass to build the arrays, then O(1) per candidate. Character comparisons run only on hash matches. The first true match ends the loop, and false matches (collisions) are so rare with M ≈ 10^9 that they add nothing on average. Space O(n) for the two arrays.

Approach 3: Optimal, the KMP prefix function

Intuition. The LPS array from KMP stores, for every prefix s[0..i], the length of its longest proper prefix that is also a suffix. Applied to the full string, its last entry lps[n - 1] is exactly the length of the longest happy prefix. No hashing and no probabilities: the result is exact and the running time is guaranteed linear.

The array is built incrementally. If len is the longest border of s[0..i-1] and s[i] == s[len], the border extends to len + 1. Otherwise, fall back to the next shorter border, which is lps[len - 1] (a border of a border is again a border), and try again until a match or len == 0.

Algorithm.

  1. Set len = 0, lps[0] = 0.
  2. For i = 1 .. n - 1: while len > 0 and s[i] != s[len], set len = lps[len - 1]. If s[i] == s[len], increment len. Store lps[i] = len.
  3. Return s[0..lps[n-1]).
static String optimal(String s) {
    int n = s.length();
    if (n == 0) return "";
    int[] lps = new int[n];
    int len = 0;
    for (int i = 1; i < n; i++) {
        while (len > 0 && s.charAt(i) != s.charAt(len)) len = lps[len - 1];
        if (s.charAt(i) == s.charAt(len)) len++;
        lps[i] = len;
    }
    return s.substring(0, lps[n - 1]);
}

Dry run on s = "ababab":

i s[i] len before action lps[i]
1 b 0 differs from s[0] = a 0
2 a 0 matches s[0] 1
3 b 1 matches s[1] 2
4 a 2 matches s[2] 3
5 b 3 matches s[3] 4

lps[5] = 4, so the answer is s[0..4) = "abab".

Complexity. Time O(n): len grows by at most one per character and each fallback shrinks it, so the fallbacks total at most n. Space O(n) for the LPS array.

The Z-function gives the same answer from another angle: the longest happy prefix has length n - i for the smallest i ≥ 1 with i + z[i] == n.

Edge cases and pitfalls