Problem statement

https://leetcode.com/problems/longest-happy-prefix/

Solution

What we need to do in this problem is to use KMP to build prefix function.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def longestPrefix(self, s):
        p = [0] * len(s)
        for i in range(1, len(s)):
            k = p[i - 1]
            while k > 0 and s[k] != s[i]:
                k = p[k - 1]
            if s[k] == s[i]:
                k += 1
            p[i] = k
        return s[:p[-1]]