Bruteforce and Rolling Hash Algorithm to Compute the Longest Happy Prefix String (Equal Prefix and Suffix)

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.

Example 1:
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:
Input: s = “ababab”
Output: “abab”
Explanation: “abab” is the largest prefix which is also suffix. They can overlap in the original string.

Example 3:
Input: s = “leetcodeleet”
Output: “leet”

Example 4:
Input: s = “a”
Output: “”

Constraints:
1 <= s.length <= 10^5
s contains only lowercase English letters.

Hints:
Use Longest Prefix Suffix (KMP-table) or String Hashing.

Bruteforce Algorithm to Compute the Longest Same Prefix and Suffix of a String

We can bruteforce each possible suffix (excluding the self), and check the suffix of the same length – to see if they are equal. Once it is equal we update the longest prefix/suffix.

1
2
3
4
5
6
7
8
9

class Solution:
    def longestPrefix(self, s: str) -> str:
        ans = ""
        for i in range(1, len(s)):
            prefix = s[:i]
            suffix = s[-i:]
            if prefix == suffix and len(prefix) > len(ans):
                ans = prefix
        return ans

class Solution:
    def longestPrefix(self, s: str) -> str:
        ans = ""
        for i in range(1, len(s)):
            prefix = s[:i]
            suffix = s[-i:]
            if prefix == suffix and len(prefix) > len(ans):
                ans = prefix
        return ans

The algorithm actually takes O(N^2) as we need to consider the complexity of taking the substring. We can actually improve the implementation of the bruteforce – to a shorter/concise version:

1
2
3
4
5
6

class Solution:
    def longestPrefix(self, s: str) -> str:
        for i in range(1, len(s)):
            if s.startswith(s[i:]):
                return s[i:]
        return ""                

class Solution:
    def longestPrefix(self, s: str) -> str:
        for i in range(1, len(s)):
            if s.startswith(s[i:]):
                return s[i:]
        return ""                

In this implementation, we check and return the first suffix (from left to right starting the first character) once it is also prefix (using the startsWith function). However, the runtime complexity is still O(N^2) due to the startsWith and string slicing.

Rolling Hash Algorith to Compute the Longest Prefix/Suffix

We can use rolling hash algorithm to improve the algorithm and reduce the runtime complexity to O(N). The string value can be computed using rolling hash – so the longest prefix/suffix should have the same hash values. The hash value for the string can be computed via the sum of each letter with different weight.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def longestPrefix(self, s: str) -> str:
        l = 0
        r = 0
        p = 1
        m = 1e9 + 7
        k = 0
        for i in range(len(s) - 1):
            l = (l * 128 + ord(s[i])) % m
            r = (r + p * ord(s[len(s) - i - 1])) % m
            if l == r:
                k = i + 1
            p = (p * 128) % m
        return s[:k]

class Solution:
    def longestPrefix(self, s: str) -> str:
        l = 0
        r = 0
        p = 1
        m = 1e9 + 7
        k = 0
        for i in range(len(s) - 1):
            l = (l * 128 + ord(s[i])) % m
            r = (r + p * ord(s[len(s) - i - 1])) % m
            if l == r:
                k = i + 1
            p = (p * 128) % m
        return s[:k]

Here, 128 is chosen as the weight. For example, ab will have hash = 128*97+98.

–EOF (The Ultimate Computing & Technology Blog) —