Longest Happy Prefix - Leetcode Solution

The problem is to find the longest prefix of a string such that the rest of the string contains only characters from that prefix. For example, for the string "abcabcabc", the answer would be "abc".

The solution to this problem involves using a prefix-suffix table. This table is built using the Knuth-Morris-Pratt (KMP) algorithm. This algorithm finds the longest proper prefix of a string that is also a suffix of that string.

The prefix-suffix table can be used to determine the length of the longest prefix of a string that matches a suffix of that string. This is because the last entry in the prefix-suffix table gives the length of the longest proper prefix that is also a suffix of the entire string. By removing this suffix from the end of the string, we can obtain the part of the string that only contains the prefix.

The algorithm to solve this problem is as follows:

1. Build the prefix-suffix table using the KMP algorithm for the string.

2. Find the length of the longest proper prefix that is also a suffix of the entire string. This can be done by looking up the last entry in the prefix-suffix table.

3. Remove this suffix from the end of the string to obtain the part of the string that only contains the prefix.

4. Return this prefix.

The time complexity of this algorithm is O(n), where n is the length of the string. This is because building the prefix-suffix table takes O(n) time and finding the prefix takes O(1) time.

Here is the Python code for this algorithm:

def longestPrefix(s: str) -> str: # Build prefix-suffix table n = len(s) pi = [0] * n j = 0 for i in range(1, n): while j > 0 and s[j] != s[i]: j = pi[j-1] if s[j] == s[i]: j += 1 pi[i] = j

# Find longest prefix
prefix_len = pi[-1]
prefix = s[:prefix_len]
return prefix

The input string is passed in as an argument to the function, and the output is the longest happy prefix of the string.

1