# Longest Happy Prefix
**Difficulty:** HARD
[External](https://leetcode.com/problems/longest-happy-prefix)
Canonical: https://scaleengineer.com/dsa/problems/longest-happy-prefix
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Data structures:** String
---
## 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 <= 105`
* `s` contains only lowercase English letters.

# Approaches
## Brute Force Iteration
This approach directly implements the problem definition. We check every possible proper prefix, from the longest to the shortest, and see if it matches the corresponding suffix of the same length. The first match we find is guaranteed to be the longest one.
**Time:** O(n^2), where n is the length of the string. The loop runs up to n-1 times. Inside the loop, `substring` creation and `equals` comparison both take O(len) time. In the worst case, this leads to a quadratic time complexity: Σ(len) for len from n-1 to 1. · **Space:** O(n), where n is the length of the string. In each iteration, we create two new substrings. The maximum length of these substrings is n-1, so the space required is proportional to n.
**Pros:** Simple to understand and implement.; Directly follows the problem definition.
**Cons:** Inefficient for large strings, likely to cause a 'Time Limit Exceeded' error on platforms with strict time limits.; Repeatedly creates new string objects, which can be memory-intensive.
### Explanation
The algorithm iterates through all possible lengths for a happy prefix, starting from the largest possible length `n-1` down to `1`, where `n` is the length of the string `s`.

In each iteration, for a given length `len`:
- We extract the prefix of length `len`: `s.substring(0, len)`.
- We extract the suffix of length `len`: `s.substring(n - len)`.
- We compare these two substrings.

If they are identical, we have found the longest happy prefix, so we return it immediately.
If the loop completes without finding any match, it means no happy prefix exists, and we return an empty string.

```java
class Solution {
    public String longestPrefix(String s) {
        int n = s.length();
        for (int len = n - 1; len > 0; len--) {
            String prefix = s.substring(0, len);
            String suffix = s.substring(n - len);
            if (prefix.equals(suffix)) {
                return prefix;
            }
        }
        return "";
    }
}
```
### Algorithm
- Let `n` be the length of the input string `s`.
- Iterate a variable `len` from `n - 1` down to `1`.
- In each iteration, get the prefix `s.substring(0, len)`.
- Get the suffix `s.substring(n - len)`.
- If the prefix equals the suffix, return the prefix.
- If the loop finishes, return an empty string `""`.

## Rolling Hash (Rabin-Karp)
This approach improves upon the brute-force method by avoiding explicit substring comparisons in every step. It uses a rolling hash function to calculate the hash values of prefixes and suffixes in constant time per step. If the hash values match, it's highly likely the strings match. This reduces the overall time complexity significantly.
**Time:** O(n) on average. The loop runs n-1 times, and each operation inside is O(1). The string verification step takes O(i) time, but it's only executed on a hash match. Assuming hash collisions are rare, this happens infrequently. In the worst case (e.g., `s = "aaaa...a"`), it degrades to O(n^2). With double hashing, it's practically O(n). · **Space:** O(1) if we don't count the space for the result string. We only use a few variables to store hashes and powers.
**Pros:** Much faster than brute force on average.; Low memory usage.
**Cons:** Susceptible to hash collisions, which might lead to incorrect results if substrings are not verified.; Worst-case time complexity is still O(n^2) if verification is included and collisions are frequent.; More complex to implement correctly than the brute-force approach.
### Explanation
The core idea is to represent substrings as numerical hash values. Comparing two hashes is an O(1) operation, much faster than comparing two strings.

We iterate from `i = 0` to `n-2`. In each step, we calculate the hash of the prefix `s[0...i]` and the suffix `s[n-1-i...n-1]`.

To do this efficiently, we maintain two hash values: `prefixHash` and `suffixHash`.
- `prefixHash` is updated by incorporating the next character `s[i]`.
- `suffixHash` is updated by incorporating the next character from the end, `s[n-1-i]`, making sure to scale it by the correct power of the base.

We also keep track of the current power of our base `p`.
If at any point `prefixHash` equals `suffixHash`, we have a potential match. We then verify this match by comparing the actual substrings to avoid issues with hash collisions. We record the length of the longest verified match found.

To further reduce the chance of collision, one could use two different hash functions (double hashing), which makes the probability of a false positive negligible, often allowing the explicit string comparison to be skipped in practice.

```java
class Solution {
    public String longestPrefix(String s) {
        long prefixHash = 0;
        long suffixHash = 0;
        long power = 1;
        long base = 31;
        long mod = 1_000_000_007;
        int n = s.length();
        int longestLen = 0;

        for (int i = 0; i < n - 1; i++) {
            // Update prefix hash (from left)
            prefixHash = (prefixHash * base + (s.charAt(i) - 'a' + 1)) % mod;

            // Update suffix hash (from right)
            suffixHash = (suffixHash + power * (s.charAt(n - 1 - i) - 'a' + 1)) % mod;
            
            // Update power of base
            power = (power * base) % mod;

            if (prefixHash == suffixHash) {
                // Potential match found, verify it
                if (s.substring(0, i + 1).equals(s.substring(n - 1 - i))) {
                    longestLen = i + 1;
                }
            }
        }
        return s.substring(0, longestLen);
    }
}
```
### Algorithm
- Choose a prime base (e.g., 31) and a large prime modulus (e.g., 10^9 + 7).
- Initialize `prefixHash = 0`, `suffixHash = 0`, `power = 1`, and `longestLen = 0`.
- Iterate `i` from `0` to `n-2`.
- Update `prefixHash` for `s[0...i]`.
- Update `suffixHash` for `s[n-1-i...n-1]`.
- Update `power` for the next iteration.
- If `prefixHash == suffixHash`, verify if `s.substring(0, i + 1)` equals `s.substring(n - 1 - i)`.
- If they are equal, update `longestLen = i + 1`.
- After the loop, return `s.substring(0, longestLen)`.

## KMP Algorithm - Longest Proper Prefix Suffix (LPS) Array
This is the most efficient and standard approach for this problem. The problem of finding the longest happy prefix is identical to finding the length of the longest proper prefix of a string that is also its suffix. This is precisely what the preprocessing step of the Knuth-Morris-Pratt (KMP) string searching algorithm calculates. We can build the KMP's Longest Proper Prefix Suffix (LPS) array, and the last value in this array will give us the length of the desired prefix.
**Time:** O(n), where n is the length of the string. The algorithm processes each character of the string once. Although the `length` pointer can move backward, the total number of operations is linear in `n` (amortized analysis), giving a guaranteed linear time performance. · **Space:** O(n) to store the `lps` array.
**Pros:** Guaranteed O(n) time complexity, making it the most efficient solution.; A standard, well-known algorithm for prefix-suffix problems.; Deterministic and does not rely on probabilities like hashing.
**Cons:** Requires extra O(n) space for the LPS array.; The logic can be less intuitive to understand compared to brute force or hashing.
### Explanation
The KMP algorithm uses an auxiliary array, `lps`, where `lps[i]` is the length of the longest proper prefix of the substring `s[0...i]` which is also a suffix of `s[0...i]`.

By definition, the longest happy prefix of the entire string `s` (of length `n`) is the longest proper prefix of `s` that is also a suffix of `s`. This corresponds exactly to the value of `lps[n-1]`.

The algorithm to build the `lps` array works in a single pass. It uses two pointers: `i` to iterate through the string `s`, and `length` to track the length of the current longest prefix-suffix.
- If `s[i]` and `s[length]` match, we extend the current prefix-suffix by incrementing `length`, and we set `lps[i] = length`.
- If they don't match, we need to find a shorter prefix-suffix to try and extend. We do this by backtracking on the `length` pointer using the already computed `lps` values: `length = lps[length - 1]`.

After computing the entire `lps` array, the length of the longest happy prefix is `lps[n-1]`. We can then return the substring of `s` of that length.

```java
class Solution {
    public String longestPrefix(String s) {
        int n = s.length();
        if (n <= 1) {
            return "";
        }
        int[] lps = new int[n];
        // lps[0] is always 0
        int length = 0; // length of the previous longest prefix suffix
        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++;
                }
            }
        }

        int longestLen = lps[n - 1];
        return s.substring(0, longestLen);
    }
}
```
### Algorithm
- Create an integer array `lps` of the same size as the string `s`.
- Initialize `lps[0] = 0`, a pointer `length = 0`, and another pointer `i = 1`.
- Iterate with `i` from `1` to `n-1`:
    - If `s.charAt(i)` matches `s.charAt(length)`, increment `length`, set `lps[i] = length`, and increment `i`.
    - If they don't match:
        - If `length` is not `0`, update `length` to `lps[length - 1]` (backtrack).
        - If `length` is `0`, set `lps[i] = 0` and increment `i`.
- The final value `lps[n-1]` gives the length of the longest happy prefix.
- Return `s.substring(0, lps[n-1])`.

# Solutions
### Java

```java
class Solution {
private
  long[] p;
private
  long[] h;
public
  String longestPrefix(String s) {
    int base = 131;
    int n = s.length();
    p = new long[n + 10];
    h = new long[n + 10];
    p[0] = 1;
    for (int i = 0; i < n; ++i) {
      p[i + 1] = p[i] * base;
      h[i + 1] = h[i] * base + s.charAt(i);
    }
    for (int l = n - 1; l > 0; --l) {
      if (get(1, l) == get(n - l + 1, n)) {
        return s.substring(0, l);
      }
    }
    return "";
  }
private
  long get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; }
}

```

### CPP

```cpp
typedef unsigned long long ULL ; class Solution { public: string longestPrefix ( string s ) { int base = 131 ; int n = s . size (); ULL p [ n + 10 ]; ULL h [ n + 10 ]; p [ 0 ] = 1 ; h [ 0 ] = 0 ; for ( int i = 0 ; i < n ; ++ i ) { p [ i + 1 ] = p [ i ] * base ; h [ i + 1 ] = h [ i ] * base + s [ i ]; } for ( int l = n - 1 ; l > 0 ; -- l ) { ULL prefix = h [ l ]; ULL suffix = h [ n ] - h [ n - l ] * p [ l ]; if ( prefix == suffix ) return s . substr ( 0 , l ); } return "" ; } };
```

### Python

```python
class Solution:
    def longestPrefix(self, s: str) -> str: for i in range(1, len(s)): if s[: - i] == s[i:]: return s[i:] return ''

```