Longest Happy Prefix

Problem

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.

Examples

Example 1:

1
2
3
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:

1
2
3
Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap in the original string.

Solution

Method 1 - Using KMP

To solve this problem, we can use the concept of the KMP (Knuth-Morris-Pratt) algorithm’s prefix function, also known as the pi function. The pi function for a string provides the length of the longest proper prefix which is also a suffix for every substring ending at each index.

Here is the approach:

Compute the KMP prefix function for the given string s.
The value at the last index of the pi array will give us the length of the longest happy prefix.
Extract the substring from the start of s up to this length.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public String longestPrefix(String s) {
        int n = s.length();
        int[] pi = new int[n];
        int j = 0;

        for (int i = 1; i < n; i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = pi[j - 1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            pi[i] = j;
        }

        return s.substring(0, pi[n - 1]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def longestPrefix(self, s: str) -> str:
        n = len(s)
        pi: List[int] = [0] * n
        j = 0

        for i in range(1, n):
            while j > 0 and s[i] != s[j]:
                j = pi[j - 1]
            if s[i] == s[j]:
                j += 1
            pi[i] = j

        return s[:pi[n - 1]]

Complexity

⏰ Time complexity: O(n), as the KMP prefix function itself is computed in O(n) time, where n is the length of the string s.
🧺 Space complexity: O(n), mainly for storing the pi array.

Problem#

Examples#

Solution#

Method 1 - Using KMP#

Code#

Complexity#