Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1508. Longest Happy Prefix

My accepted Python solution to LeetCode problem 1508, Longest Happy Prefix, running in 93ms.

  • Difficulty: Hard
  • Python
  • Runtime 93ms
  • Memory 21.7MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 93ms, memory 21.7MB, accepted 2025-12-29.

python
class Solution:
    def longestPrefix(self, s: str) -> str:
        # KMP failure function / LPS (Longest Proper Prefix which is also Suffix)
        # Time: O(n), Space: O(n)
        n = len(s)
        if n == 0:
            return ""
        
        # lps[i] = length of longest proper prefix which is also suffix for s[0:i+1]
        lps = [0] * n
        
        length = 0  # length of previous longest prefix suffix
        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
        
        # The answer is s[0:lps[n-1]]
        return s[:lps[n-1]]

Source