Longest Happy Prefix LeetCode solution in Python

1
# Runtime: 186 ms (Top 90.2%) | Memory: 21.02 MB (Top 32.3%)
2

3

4
class Solution:
5
    def longestPrefix(self, s: str) -> str:
6
        n = len(s)
7
        lps = [0] * n
8
        j = 0
9
        for i in range(1, n):
10
            while s[i] != s[j] and j > 0:
11
                j = lps[j - 1]
12

13
            if s[i] == s[j]:
14
                lps[i] = j + 1
15
                j += 1
16

17
        return s[: lps[-1]]