Given a string, s, find the longest happy prefix. If no such prefix exists, return an empty string "".
Note: A happy prefix of a string is a non-empty substring at the beginning that also appears at the end (but not the entire string itself).
Constraints:
s.length
s contains only lowercase English letters.
A Longest Happy Prefix in a string is a non-empty substring that appears at the beginning and end of the string. One way to tackle this problem is to use a hash map approach. The idea is to iterate over the string while building all possible prefixes and storing each in a hash map. Simultaneously, we build the corresponding suffix (from right to left) and check if that suffix is already present in the hash map. If we find a match, we keep track of the length of the matched substring. This method is often an intuitive first attempt because it directly uses substring membership checks in a hash structure, but it can lead to quadratic time complexity since, at each step, we are constructing strings of increasing length, and storing or comparing them can be quite expensive.
We can evolve this solution into a rolling hash to make the process more efficient. Instead of storing actual substrings in a hash map, we keep track of numerical hash values that represent those substrings. We choose a base and a large prime modulus and treat each prefix and suffix as a polynomial in that base. With each new character, we can update the hash of the current prefix in constant time by multiplying the previous hash by the base, adding the new character’s value, and taking the result modulo our large prime. We do a similar process for the suffix from the right side, only adjusting our multiplication factors accordingly. Whenever these two hash values (for the prefix and the suffix) are equal, we infer that the substrings are likely the same (assuming collisions are unlikely with good parameter choices), and we can record the potential new longest matching prefix. This rolling hash technique avoids repeatedly storing or comparing large substrings, typically running in linear time.
Rolling hash concept:
Polynomial rolling hash: We treat each substring as a number in a positional numeral system. For a string
where:
Given a string, s, find the longest happy prefix. If no such prefix exists, return an empty string "".
Note: A happy prefix of a string is a non-empty substring at the beginning that also appears at the end (but not the entire string itself).
Constraints:
s.length
s contains only lowercase English letters.
A Longest Happy Prefix in a string is a non-empty substring that appears at the beginning and end of the string. One way to tackle this problem is to use a hash map approach. The idea is to iterate over the string while building all possible prefixes and storing each in a hash map. Simultaneously, we build the corresponding suffix (from right to left) and check if that suffix is already present in the hash map. If we find a match, we keep track of the length of the matched substring. This method is often an intuitive first attempt because it directly uses substring membership checks in a hash structure, but it can lead to quadratic time complexity since, at each step, we are constructing strings of increasing length, and storing or comparing them can be quite expensive.
We can evolve this solution into a rolling hash to make the process more efficient. Instead of storing actual substrings in a hash map, we keep track of numerical hash values that represent those substrings. We choose a base and a large prime modulus and treat each prefix and suffix as a polynomial in that base. With each new character, we can update the hash of the current prefix in constant time by multiplying the previous hash by the base, adding the new character’s value, and taking the result modulo our large prime. We do a similar process for the suffix from the right side, only adjusting our multiplication factors accordingly. Whenever these two hash values (for the prefix and the suffix) are equal, we infer that the substrings are likely the same (assuming collisions are unlikely with good parameter choices), and we can record the potential new longest matching prefix. This rolling hash technique avoids repeatedly storing or comparing large substrings, typically running in linear time.
Rolling hash concept:
Polynomial rolling hash: We treat each substring as a number in a positional numeral system. For a string
where: