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.