Problem Description

Given a string s, you are asked to find the longest prefix of s which is also a suffix (but not equal to the entire string itself). This is known as the "Longest Happy Prefix".

Formally, you need to find the longest non-empty string pre such that pre is both a prefix and a suffix of s, and pre != s.

Constraints:

• The input string s consists of lowercase English letters.
• The length of s is up to 10⁵.
• There is always one valid answer (possibly the empty string).

Thought Process

At first glance, the problem seems to invite a brute-force approach: for every possible prefix (except the full string), check if it also matches the corresponding suffix. However, this would be inefficient, especially for long strings.

To optimize, we need a way to efficiently compare prefixes and suffixes. This is reminiscent of the string matching algorithms, especially the Knuth-Morris-Pratt (KMP) algorithm, which preprocesses the string to find such overlaps.

The key insight is: for every prefix ending at position i, we want to know the length of the longest proper prefix which is also a suffix. This information is exactly what the KMP "lps" (longest prefix-suffix) array gives us.

Solution Approach

We use the KMP preprocessing algorithm to solve this problem efficiently.

• We initialize an array lps of size n (where n is the length of s), where lps[i] will store the length of the longest prefix which is also a suffix for the substring s[0..i].
• We iterate through the string, and for each character, we try to extend the current matching prefix and suffix. If the characters match, we increase the length of the current prefix-suffix; otherwise, we backtrack using the lps array.
• At the end, lps[n-1] gives the length of the longest prefix which is also a suffix (but not the whole string).
• We return s[0:lps[n-1]] as the answer. If lps[n-1] is 0, we return an empty string.

This approach is efficient and avoids redundant comparisons.

Example Walkthrough

Let's take the input s = "level".

• Prefixes: "l", "le", "lev", "leve"
• Suffixes: "l", "el", "vel", "evel"
• We look for the longest string which is both a prefix and a suffix, but not the whole string. Here, "l" is both a prefix and suffix, but nothing longer.
• So, the answer is "l".

Another example: s = "ababab"

• Prefixes: "a", "ab", "aba", "abab", "ababa"
• Suffixes: "b", "ab", "bab", "abab", "babab"
• The longest happy prefix is "abab".
• With KMP, the lps array is [0,0,1,2,3,4], so the answer is s[0:4] = "abab".

Time and Space Complexity

Brute-force approach:

• For each possible prefix of length k, compare with the corresponding suffix, leading to O(n²) time in the worst case.

• Building the lps array takes O(n) time, since we only ever move forward or back by the prefix length.
• Space complexity is O(n) for the lps array.
• This is optimal for the input size constraints.

Summary

The "Longest Happy Prefix" problem asks for the longest prefix of a string that is also a suffix (but not the whole string). While a brute-force solution is possible, it is inefficient for large inputs. By leveraging the KMP algorithm's preprocessing step, we can efficiently compute the answer in linear time. The solution is elegant because it reuses a classic algorithmic technique for a slightly different string overlap problem, making it both efficient and robust.

Code Implementation

class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        lps = [0] * n
        length = 0  # length of the previous longest prefix suffix

        for i in range(1, n):
            while length > 0 and s[i] != s[length]:
                length = lps[length - 1]
            if s[i] == s[length]:
                length += 1
                lps[i] = length
            else:
                lps[i] = 0
        return s[:lps[-1]]
      

class Solution {
public:
    string longestPrefix(string s) {
        int n = s.size();
        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;
            } else {
                lps[i] = 0;
            }
        }
        return s.substr(0, lps[n - 1]);
    }
};
      

class Solution {
    public String longestPrefix(String s) {
        int n = s.length();
        int[] lps = new int[n];
        int length = 0;
        for (int i = 1; i < n; i++) {
            while (length > 0 && s.charAt(i) != s.charAt(length)) {
                length = lps[length - 1];
            }
            if (s.charAt(i) == s.charAt(length)) {
                length++;
                lps[i] = length;
            } else {
                lps[i] = 0;
            }
        }
        return s.substring(0, lps[n - 1]);
    }
}
      

var longestPrefix = function(s) {
    const n = s.length;
    const lps = new Array(n).fill(0);
    let length = 0;
    for (let 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;
        } else {
            lps[i] = 0;
        }
    }
    return s.slice(0, lps[n - 1]);
};