1392. Longest Happy Prefix
Approach
Rolling hash; simultaneously compute prefix hash from left and suffix hash from right; track longest matching pair.
Key Techniques
String problems range from simple character counting to complex pattern matching. Common approaches include two pointers, sliding window, prefix hashing, and the KMP algorithm. In C#, strings are immutable — use StringBuilder for efficient concatenation inside loops.
String matching finds occurrences of a pattern in text. KMP runs in O(n+m) using a failure function to skip redundant comparisons. Rabin-Karp uses rolling hashes for average O(n+m). Z-algorithm and suffix arrays support more general substring queries.
Custom hash functions reduce collisions in hash maps. Polynomial rolling hash H(s) = s[0]·pⁿ⁻¹ + ... + s[n-1] is common for strings. Use double hashing (two independent hashes) to reduce collision probability to near zero.
// Approach: Rolling hash; simultaneously compute prefix hash from left and suffix hash from right; track longest matching pair.
// Time: O(n) Space: O(1)
public class Solution
{
public string LongestPrefix(string s)
{
const int kBase = 26;
const long kHash = 8417508174513L;
int n = s.Length;
int maxLength = 0;
long pow = 1;
long prefixHash = 0; // the hash of s[0..i]
long suffixHash = 0; // the hash of s[j..n)
for (int i = 0, j = n - 1; i < n - 1; ++i, --j)
{
prefixHash = (prefixHash * kBase + Val(s[i])) % kHash;
suffixHash = (Val(s[j]) * pow + suffixHash) % kHash;
pow = pow * kBase % kHash;
if (prefixHash == suffixHash)
maxLength = i + 1;
}
return s.Substring(0, maxLength);
}
private int Val(char c)
{
return c - 'a';
}
}