Longest Happy Prefix

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 <= 10^5
• s contains only lowercase English letters.

class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        for length in range(n - 1, 0, -1):
            if s[:length] == s[n-length:]:
                return s[:length]
        return ""

Naive Solution

The naive solution iterates through all possible prefix lengths from n-1 down to 1. For each length, it checks if the prefix of that length is equal to the suffix of the same length. If a match is found, it returns the prefix. If no match is found after checking all possible lengths, it returns an empty string.

Optimal Solution

The optimal solution uses the Knuth-Morris-Pratt (KMP) algorithm to compute the longest proper prefix which is also a suffix for each prefix of the string. This is done by constructing a "longest prefix suffix" (LPS) array. The last element of the LPS array gives the length of the longest happy prefix.

class Solution:
    def longestPrefix(self, 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[n - 1]]

Big(O) Run-time Analysis

• Naive Solution: The outer loop iterates n-1 times, and the string comparison s[:length] == s[n-length:] takes O(length) time in the worst case. Since length can be up to n-1, the worst-case time complexity is O(n^2).
• Optimal Solution: The KMP algorithm computes the LPS array in O(n) time because each character in the string is visited a constant number of times. The construction of the prefix also takes O(n) time at most. Thus, the overall runtime is O(n).

Big(O) Space Usage Analysis

• Naive Solution: The naive solution uses only constant extra space, so the space complexity is O(1).
• Optimal Solution: The KMP algorithm uses an LPS array of size n, so the space complexity is O(n).

Edge Cases

1. Empty String: While the constraint specifies that the string length is at least 1, it's good to consider what would happen with an empty string. The code handles this gracefully (although it won't occur based on the problem statement).
2. String with no happy prefix: For example, "abcde". The algorithms correctly return an empty string.
3. String where the entire string (excluding itself) is a happy prefix: For example, "abab". The algorithm correctly identifies and returns the longest such prefix.
4. Single-character string: For example, "a". The algorithm returns an empty string, as expected because a happy prefix must be non-empty and exclude the entire string.
5. String with overlapping prefixes and suffixes: For example, "ababab". The algorithm correctly identifies "abab" as the longest happy prefix.