Longest happy prefix

String Rolling Hash String Matching Hash Function

51.9% acceptance

Feb 25, 2026

1576

A string is called a happy prefix if is a non-empty prefix which is also a suffix (excluding itself). Given a string s, return the longest happy prefix of s. Return an empty string "" if no such prefix exists.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_prefix(s: String) -> String {
    let s = s.as_bytes();
    let n = s.len();
    // KMP failure function
    let mut fail = vec![0usize; n];
    let mut k = 0usize;
    for i in 1..n {
      while k > 0 && s[k] != s[i] { k = fail[k - 1]; }
      if s[k] == s[i] { k += 1; }
      fail[i] = k;
    }
    let len = fail[n - 1];
    String::from_utf8(s[..len].to_vec()).unwrap()
  }
}