Longest Happy Prefix solution and explanation
Google
9 more videos on this problem
KMP Algorithm - Longest Happy Prefix | Covering ALL DSA Patterns in Coding InterviewsBharat Khanna · 26:57 · 4K views
LeetCode 1392. Longest Happy PrefixHappy Coding · 34:41 · 4K views
1392. Longest Happy Prefix | Pi tableRaman Bhari · 13:59 · 3K views
【每日一题】1392. Longest Happy Prefix, 2/2/2021Huifeng Guan · 31:21 · 1K views
1392. Longest Happy Prefix | Java | Leetcode | Strings | DSACoding with Tamilarasan · 17:03 · 768 views
Longest Happy Prefix - Leetcode 1392 | Using LPS | Python | College Wala DostCollege Wala Dost · 6:54 · 653 views
Leetcode 1392. Longest Happy PrefixFearless Learner · 2:27 · 178 views
Leetcode 1392. Longest Happy Prefix (kmp)LetsCode · 7:24 · 140 views
1392. Longest Happy PrefixJust Coding, with Jie · 13:24 · 106 views
LeetCode 1392: Longest Happy PrefixAlitaCode · 23:07 · 16 views
The problem
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.
Example 1:
Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"), and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix is given by "l".
Example 2:
Input: s = "ababab" Output: "abab" Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.
Constraints:
1 <= s.length <= 105scontains only lowercase English letters.
Approach overview
Problem Overview: Given a string s, return the longest prefix that is also a suffix of the same string, excluding the entire string itself. The prefix and suffix must be identical in characters and order. If none exists, return an empty string.
Approach 1: Brute Force Prefix Check (O(n²) time, O(1) space)
Start from the longest possible prefix length n-1 and move backward. For each length k, compare s[0:k] with the suffix s[n-k:n]. The first match you find is the longest happy prefix. This approach relies on repeated substring comparisons, which makes it quadratic in the worst case when many prefixes partially match. It works for small strings but quickly becomes slow when n grows.
Approach 2: KMP Prefix Function (O(n) time, O(n) space)
This is the most common solution using the prefix function from the string matching family of algorithms. Build the LPS (longest prefix suffix) array used in the Knuth–Morris–Pratt algorithm. While iterating through the string, the array stores the length of the longest prefix that also matches a suffix ending at that index. After processing the full string, lps[n-1] directly gives the length of the longest happy prefix. The key insight is that KMP reuses previous prefix information instead of rechecking characters, which guarantees linear time.
Approach 3: Rolling Hash (O(n) time, O(1) space)
A hashing-based approach compares prefix and suffix hashes as you scan the string from both directions. Maintain a forward rolling hash for the prefix and a backward hash for the suffix. When the two hash values match, record the current length as a candidate answer. With a good base and modulus, hash collisions are extremely rare. This method relies on techniques from rolling hash and hash functions, allowing constant-time hash updates per character.
Recommended for interviews: The KMP prefix-function solution is what most interviewers expect. It demonstrates understanding of classic string algorithms and avoids redundant comparisons. The brute force method shows you understand the definition of prefix and suffix, but the linear-time KMP solution proves you can optimize string matching problems effectively. Rolling hash is also acceptable in interviews, especially if you already know polynomial hashing.
Approach 1: KMP Algorithm
The KMP (Knuth-Morris-Pratt) algorithm is an efficient string matching algorithm that includes preprocessing the pattern (or string in this case) to construct a partially matched table, which can be utilized to identify proper prefixes which are also suffixes.
By utilizing this table, we can find the longest happy prefix by examining the last value of this table.
def longestPrefix(s: str) -> str:
n = len(s)
lps = [0] * n
length = 0
i = 1
while i < n:
if s[i] == s[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return s[:lps[-1]]
print(longestPrefix("level"))public class LongestHappyPrefix {
public static String longestPrefix(String s) {
int n = s.length();
int[] lps = new int[n];
int length = 0;
int i = 1;
while (i < n) {
if (s.charAt(i) == s.charAt(length)) {
length++;
lps[i] = length;
i++;
} else {
if (length != 0) {
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return s.substring(0, lps[n - 1]);
}
public static void main(String[] args) {
String s = "ababab";
System.out.println(longestPrefix(s));
}
}#include <iostream>
#include <vector>
#include <string>
std::string longestPrefix(std::string s) {
int n = s.size();
std::vector<int> lps(n, 0);
int length = 0;
for (int i = 1; i < n; i++) {
while (length > 0 && s[i] != s[length]) {
length = lps[length - 1];
}
if (s[i] == s[length]) {
length++;
}
lps[i] = length;
}
return s.substr(0, lps[n - 1]);
}
int main() {
std::string s = "level";
std::cout << longestPrefix(s) << std::endl;
return 0;
}function longestPrefix(s) {
const n = s.length;
const lps = Array(n).fill(0);
let length = 0;
let i = 1;
while (i < n) {
if (s[i] === s[length]) {
length++;
lps[i] = length;
i++;
} else {
if (length !== 0) {
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return s.slice(0, lps[n - 1]);
}
console.log(longestPrefix("level"));#include <stdio.h>
#include <string.h>
void computeLPSArray(char* s, int sLen, int* lps) {
int length = 0;
lps[0] = 0;
int i = 1;
while (i < sLen) {
if (s[i] == s[length]) {
length++;
lps[i] = length;
i++;
}
else {
if (length != 0) {
length = lps[length - 1];
}
else {
lps[i] = 0;
i++;
}
}
}
}
char* longestPrefix(char* s) {
int sLen = strlen(s);
int lps[sLen];
computeLPSArray(s, sLen, lps);
int length = lps[sLen - 1];
char* result = malloc((length + 1) * sizeof(char));
strncpy(result, s, length);
result[length] = '\0';
return result;
}
int main() {
char s[] = "ababab";
printf("%s\n", longestPrefix(s));
return 0;
}public class Solution {
public string LongestPrefix(string s) {
int n = s.Length;
int[] lps = new int[n];
int length = 0;
int i = 1;
while (i < n) {
if (s[i] == s[length]) {
length++;
lps[i] = length;
i++;
} else {
if (length != 0) {
length = lps[length - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return s.Substring(0, lps[n - 1]);
}
public static void Main() {
Console.WriteLine(new Solution().LongestPrefix("ababab"));
}
}The Python solution is straightforward, leveraging the KMP table construction for detecting the longest prefix that is a suffix. It handles all edge cases by resetting the match count (length) based on prior computations when mismatches occur.
Time Complexity: O(n) allows efficient traversal during LPS calculation.
Space Complexity: O(n) dedicated to LPS tracking.
Approach 2: Rolling Hash
This approach leverages computation of hash values to dynamically relate prefixes and suffixes. We incrementally maintain prefix hash and suffix hash values following pattern matching principles. Equal hashes upon completion indicate potential matching of prefix and suffix. This strategy takes advantage of properties of polynomial rolling hashes.
def longestPrefix(s: str) -> str:
n = len(s)
prefix_hash, suffix_hash, base_pow = 0, 0, 1
length = 0
MOD, BASE = 1000000007, 31
for i in range(n - 1):
prefix_hash = (prefix_hash * BASE + (ord(s[i]) - ord('a') + 1)) % MOD
suffix_hash = (suffix_hash + (ord(s[n - i - 1]) - ord('a') + 1) * base_pow) % MOD
base_pow = (base_pow * BASE) % MOD
if prefix_hash == suffix_hash:
length = i + 1
return s[:length]
print(longestPrefix("level"))public class LongestHappyPrefix {
static final int MOD = 1000000007;
static final int BASE = 31;
public static String longestPrefix(String s) {
int n = s.length();
long prefixHash = 0, suffixHash = 0, basePow = 1;
int length = 0;
for (int i = 0, j = n - 1; j > 0; i++, j--) {
prefixHash = (prefixHash * BASE + (s.charAt(i) - 'a' + 1)) % MOD;
suffixHash = (suffixHash + (s.charAt(j) - 'a' + 1) * basePow) % MOD;
basePow = (basePow * BASE) % MOD;
if (prefixHash == suffixHash) {
length = i + 1;
}
}
return s.substring(0, length);
}
public static void main(String[] args) {
String s = "ababab";
System.out.println(longestPrefix(s));
}
}#include <iostream>
#include <string>
#define MOD 1000000007
#define BASE 31
std::string longestPrefix(std::string s) {
int n = s.size();
if (n == 0) return "";
long long prefixHash = 0, suffixHash = 0, basePow = 1;
int length = 0;
for (int i = 0, j = n - 1; j > 0; i++, j--) {
prefixHash = (prefixHash * BASE + (s[i] - 'a' + 1)) % MOD;
suffixHash = (suffixHash + (s[j] - 'a' + 1) * basePow) % MOD;
basePow = (basePow * BASE) % MOD;
if (prefixHash == suffixHash) {
length = i + 1;
}
}
return s.substr(0, length);
}
int main() {
std::string s = "level";
std::cout << longestPrefix(s) << std::endl;
return 0;
}function longestPrefix(s) {
const MOD = 1000000007, BASE = 31;
const n = s.length;
let prefixHash = 0, suffixHash = 0, basePow = 1;
let length = 0;
for (let i = 0, j = n - 1; j > 0; i++, j--) {
prefixHash = (prefixHash * BASE + (s.charCodeAt(i) - 'a'.charCodeAt(0) + 1)) % MOD;
suffixHash = (suffixHash + (s.charCodeAt(j) - 'a'.charCodeAt(0) + 1) * basePow) % MOD;
basePow = (basePow * BASE) % MOD;
if (prefixHash === suffixHash) {
length = i + 1;
}
}
return s.slice(0, length);
}
console.log(longestPrefix("level"));#include <stdio.h>
#include <string.h>
#define MOD 1000000007
#define BASE 31
char* longestPrefix(char* s) {
int n = strlen(s);
if (n == 0) return "";
long prefixHash = 0, suffixHash = 0, basePow = 1;
int length = 0;
for (int i = 0, j = n - 1; j > 0; i++, j--) {
prefixHash = (prefixHash * BASE + (s[i] - 'a' + 1)) % MOD;
suffixHash = (suffixHash + (s[j] - 'a' + 1) * basePow) % MOD;
basePow = (basePow * BASE) % MOD;
if (prefixHash == suffixHash) {
length = i + 1;
}
}
char* result = (char*)malloc((length + 1) * sizeof(char));
strncpy(result, s, length);
result[length] = '\0';
return result;
}
int main() {
char s[] = "ababab";
printf("%s\n", longestPrefix(s));
return 0;
}public class Solution {
static int MOD = 1000000007;
static int BASE = 31;
public string LongestPrefix(string s) {
int n = s.Length;
long prefixHash = 0, suffixHash = 0, basePow = 1;
int length = 0;
for (int i = 0, j = n - 1; j > 0; i++, j--) {
prefixHash = (prefixHash * BASE + (s[i] - 'a' + 1)) % MOD;
suffixHash = (suffixHash + (s[j] - 'a' + 1) * basePow) % MOD;
basePow = (basePow * BASE) % MOD;
if (prefixHash == suffixHash) {
length = i + 1;
}
}
return s.Substring(0, length);
}
public static void Main() {
Console.WriteLine(new Solution().LongestPrefix("ababab"));
}
}In Python, the solution implements the rolling hash concept to dynamically relate prefix-suffix equality states. Ascertain length by computing both forward and reverse hashes. Complexity is managed using modulus arithmetic to avoid overflow.
Time Complexity: O(n) is managed by single pass hash calculations.
Space Complexity: O(1), focused on scalar space preserves, aside from the primary string.
Approach 3: String Hashing
String Hashing is a method to map a string of any length to a non-negative integer, with the probability of collision being almost zero. String hashing is used to calculate the hash value of a string, which allows for quick determination of whether two strings are equal.
We choose a fixed value BASE, and consider the string as a number in BASE radix, assigning a value greater than 0 to represent each character. Generally, the values we assign are much smaller than BASE. For example, for strings composed of lowercase letters, we can assign a=1, b=2, ..., z=26. We choose a fixed value MOD, and calculate the remainder of the BASE radix number divided by MOD, which is used as the hash value of the string.
Generally, we choose BASE=131 or BASE=13331, at which point the probability of hash value collision is extremely low. As long as the hash values of two strings are the same, we consider the two strings to be equal. Usually, MOD is chosen as 2^{64}. In C++, we can directly use the unsigned long long type to store this hash value. When calculating, we do not handle arithmetic overflow. When overflow occurs, it is equivalent to automatically taking the modulus of 2^{64}, which can avoid inefficient modulus operations.
Except for extremely specially constructed data, the above hash algorithm is unlikely to produce collisions. In general, the above hash algorithm can appear in the standard answers of the problem. We can also choose some appropriate values of BASE and MOD (such as large prime numbers), and perform several groups of hash operations. Only when the results are all the same do we consider the original strings to be equal, making it even more difficult to construct data that causes this hash to produce errors.
function longestPrefix(s: string): string {
const n = s.length;
for (let i = n - 1; i >= 0; i--) {
if (s.slice(0, i) === s.slice(n - i, n)) {
return s.slice(0, i);
}
}
return '';
}func longestPrefix(s string) string {
base := 131
n := len(s)
p := make([]int, n+10)
h := make([]int, n+10)
p[0] = 1
for i, c := range s {
p[i+1] = p[i] * base
h[i+1] = h[i]*base + int(c)
}
for l := n - 1; l > 0; l-- {
prefix, suffix := h[l], h[n]-h[n-l]*p[l]
if prefix == suffix {
return s[:l]
}
}
return ""
}impl Solution {
pub fn longest_prefix(s: String) -> String {
let n = s.len();
for i in (0..n).rev() {
if s[0..i] == s[n - i..n] {
return s[0..i].to_string();
}
}
String::new()
}
}Approach 4: KMP Algorithm
According to the problem description, we need to find the longest happy prefix of a string, which is the longest prefix of the string that is also a suffix of the string. We can use the KMP algorithm to solve this problem.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the string.
function longestPrefix(s: string): string {
s += '#';
const n = s.length;
const next: number[] = Array(n).fill(0);
next[0] = -1;
for (let i = 2, j = 0; i < n; ) {
if (s[i - 1] === s[j]) {
next[i++] = ++j;
} else if (j > 0) {
j = next[j];
} else {
next[i++] = 0;
}
}
return s.slice(0, next[n - 1]);
}func longestPrefix(s string) string {
s += "#"
n := len(s)
next := make([]int, n)
next[0], next[1] = -1, 0
for i, j := 2, 0; i < n; {
if s[i-1] == s[j] {
j++
next[i] = j
i++
} else if j > 0 {
j = next[j]
} else {
next[i] = 0
i++
}
}
return s[:next[n-1]]
}Complexity comparison
| Approach | Complexity |
|---|---|
| KMP Algorithm | Time Complexity: |
| Rolling Hash | Time Complexity: |
| String Hashing | – |
| KMP Algorithm | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Prefix Comparison | O(n²) | O(1) | Simple implementation or very small input sizes |
| KMP Prefix Function (LPS Array) | O(n) | O(n) | Standard interview solution for string prefix-suffix problems |
| Rolling Hash | O(n) | O(1) | Useful when hashing utilities are already implemented or when comparing multiple substrings |
Frequently asked questions
Is Longest Happy Prefix easy or hard?
LeetCode classifies this problem as Hard because it requires knowledge of advanced string algorithms. Developers familiar with KMP or rolling hash usually solve it quickly, but recognizing that prefix-function preprocessing applies here can be challenging for beginners.
Longest Happy Prefix Python/Java solution
Python and Java implementations usually follow the KMP prefix-function approach. Build the LPS array in a single pass through the string, then return s.substring(0, lps[n-1]) (or slicing in Python). The algorithm runs in O(n) time and O(n) space.
How to solve Longest Happy Prefix in O(n)?
Use the KMP prefix function. Build an array where each index stores the length of the longest prefix that matches a suffix ending at that position. After processing the string, the value at the last index gives the length of the longest happy prefix, which can be returned using substring extraction.
What is the best approach for Longest Happy Prefix?
The KMP prefix function approach is the most reliable solution. It builds the LPS (longest prefix suffix) array in O(n) time and directly returns the length of the longest prefix that is also a suffix. This method avoids repeated comparisons and is the approach most interviewers expect.
Is Longest Happy Prefix asked at Google/Amazon/Meta?
String matching problems like this appear in interviews at companies such as Google, Amazon, and Meta. Variants involving prefix-suffix matching, KMP preprocessing, or substring hashing are common in algorithm rounds focused on string processing.
What data structure is used in Longest Happy Prefix?
The main structure is an integer array called the LPS (longest prefix suffix) array used by the KMP algorithm. In the rolling hash approach, integer hash values and modular arithmetic are used to represent prefixes and suffixes efficiently.
What is the time complexity of Longest Happy Prefix?
The optimal solutions run in O(n) time where n is the length of the string. Both the KMP prefix-function algorithm and the rolling hash method process each character once. A naive brute force approach can degrade to O(n^2) because it repeatedly compares substrings.