38 · Segment Trees, Fenwick & String Matching

#1392 Longest Happy Prefix

frequently reported atApple Amazon Google Microsoft Meta

the problem

In plain words

A happy prefix is a non-empty prefix that is also a suffix, excluding the whole string. Return the longest happy prefix of s, or "" if there is none.

in s = "level"

out "l"

in s = "ababab"

out "abab"

Prefix and suffix may overlap.

1 ≤ s.length ≤ 10⁵
Lowercase English letters

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternKMP / prefix function Rolling hash (Rabin–Karp)

This is literally the definition of lps[n−1]. The prefix function answers it for every prefix in one O(n) pass.

solutions

From brute force to optimal

From the longest length down, check whether the prefix equals the suffix.

For len = n−1 down to 1.
If s starts with its last len characters, return them.

timeO(n²)

Up to n lengths, each comparison up to n characters.

spaceO(n)

The substring copy.

javajava.util.*

1class Solution {2    public String longestPrefix(String s) {3        int n = s.length();4        for (int len = n - 1; len > 0; len--)               // try the longest candidate first5            if (s.startsWith(s.substring(n - len))) return s.substring(0, len);6        return "";7    }8}

Precompute polynomial prefix hashes so any substring hash is O(1); compare prefix vs suffix hashes, longest first.

h[i] = hash of s[0..i), pow[i] = BASE^i.
suffix hash = h[n] − h[n−len]·pow[len] (mod).
On equal hashes verify with regionMatches and return.

timeO(n) expected

O(1) per length; verification runs once for the true answer and only rarely for collisions.

spaceO(n)

Hash and power arrays.

javajava.util.*

1class Solution {2    private static final long MOD = 1_000_000_007L, BASE = 131;3 4    public String longestPrefix(String s) {5        int n = s.length();6        long[] h = new long[n + 1], pow = new long[n + 1]; // h[i] = hash of s[0..i)7        pow[0] = 1;8        for (int i = 0; i < n; i++) {9            h[i + 1] = (h[i] * BASE + s.charAt(i)) % MOD;10            pow[i + 1] = pow[i] * BASE % MOD;11        }12        for (int len = n - 1; len > 0; len--) {13            long prefix = h[len];14            long suffix = ((h[n] - h[n - len] * pow[len]) % MOD + MOD) % MOD; // hash of s[n-len..n)15            if (prefix == suffix && s.regionMatches(0, s, n - len, len))        // verify: rule out collisions16                return s.substring(0, len);17        }18        return "";19    }20}

Build lps; the answer is s.substring(0, lps[n−1]).

len = 0; for i from 1: while mismatch, len = lps[len−1].
On match len++; lps[i] = len.
Return s[0..lps[n−1]).

timeO(n)

len rises at most n times in total, so it can fall at most n times.

spaceO(n)

The lps array.

javajava.util.*

1class Solution {2    public String longestPrefix(String s) {3        int n = s.length();4        int[] lps = new int[n]; // lps[i] = longest proper prefix of s[0..i] that is also its suffix5        for (int i = 1, len = 0; i < n; i++) {6            while (len > 0 && s.charAt(i) != s.charAt(len))7                len = lps[len - 1];                  // shrink to the next shorter border8            if (s.charAt(i) == s.charAt(len)) len++; // the border grows by one9            lps[i] = len;10        }11        return s.substring(0, lps[n - 1]);12    }13}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public String longestPrefix(String s) {3        int n = s.length();4        int[] lps = new int[n]; // lps[i] = longest proper prefix of s[0..i] that is also its suffix5        for (int i = 1, len = 0; i < n; i++) {6            while (len > 0 && s.charAt(i) != s.charAt(len))7                len = lps[len - 1];                  // shrink to the next shorter border8            if (s.charAt(i) == s.charAt(len)) len++; // the border grows by one9            lps[i] = len;10        }11        return s.substring(0, lps[n - 1]);12    }13}

in the room

How to say it in the interview

talk track

Say: "this is the KMP failure function of the whole string" — interviewers want to hear you recognise it.
Walk one fallback on the board: in "aabaaab" at i = 5, len = 2 but s[5] = 'a' ≠ s[2] = 'b', so len falls to lps[1] = 1; then s[5] = s[1] and len grows back to 2.

traps

Allowing the whole string as an answer — a happy prefix must be proper.
Hash approach without verification: wrong on collisions.

what they ask next

Follow-ups

All borders, not just the longest?

Follow the chain lps[n−1], lps[lps[n−1]−1], … down to 0 — each is a border.

before you submit

Edge cases to test

One character → ""
All the same letter: "aaaa" → "aaa" (prefix and suffix may overlap)
No border at all → ""
A border inside a border: "abacaba" → "aba"

practise next