LeetCode 题解工作台
最长快乐前缀
「快乐前缀」 是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。 给你一个字符串 s ，请你返回它的 最长快乐前缀 。如果不存在满足题意的前缀，则返回一个空字符串 "" 。 示例 1： 输入： s = "level" 输出： "l" 解释： 不包括 s 自己，一共有 4 个前缀（…
4
题型
6
代码语言
3
相关题
当前训练重点
困难 · string·结合·rolling·哈希
答案摘要
字符串哈希是把一个任意长度的字符串映射成一个非负整数，并且其冲突的概率几乎为 0。字符串哈希用于计算字符串哈希值，快速判断两个字符串是否相等。 取一固定值 BASE，把字符串看作是 BASE 进制数，并分配一个大于 0 的数值，代表每种字符。一般来说，我们分配的数值都远小于 BASE。例如，对于小写字母构成的字符串，可以令 a=1, b=2, ..., z=26。取一固定值 MOD，求出该 BAS…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 string·结合·rolling·哈希 题型思路
题目描述
「快乐前缀」 是在原字符串中既是 非空 前缀也是后缀（不包括原字符串自身）的字符串。
给你一个字符串 s，请你返回它的 最长快乐前缀。如果不存在满足题意的前缀，则返回一个空字符串 "" 。
示例 1：
输入：s = "level" 输出："l" 解释：不包括 s 自己，一共有 4 个前缀（"l", "le", "lev", "leve"）和 4 个后缀（"l", "el", "vel", "evel"）。最长的既是前缀也是后缀的字符串是 "l" 。
示例 2：
输入：s = "ababab" 输出："abab" 解释："abab" 是最长的既是前缀也是后缀的字符串。题目允许前后缀在原字符串中重叠。
提示：
1 <= s.length <= 105s只含有小写英文字母
解题思路
方法一：字符串哈希
字符串哈希是把一个任意长度的字符串映射成一个非负整数，并且其冲突的概率几乎为 0。字符串哈希用于计算字符串哈希值，快速判断两个字符串是否相等。
取一固定值 BASE，把字符串看作是 BASE 进制数，并分配一个大于 0 的数值，代表每种字符。一般来说，我们分配的数值都远小于 BASE。例如，对于小写字母构成的字符串，可以令 a=1, b=2, ..., z=26。取一固定值 MOD，求出该 BASE 进制对 M 的余数，作为该字符串的 hash 值。
一般来说，取 BASE=131 或者 BASE=13331，此时 hash 值产生的冲突概率极低。只要两个字符串 hash 值相同，我们就认为两个字符串是相等的。通常 MOD 取 2^64，C++ 里，可以直接使用 unsigned long long 类型存储这个 hash 值，在计算时不处理算术溢出问题，产生溢出时相当于自动对 2^64 取模，这样可以避免低效取模运算。
除了在极特殊构造的数据上，上述 hash 算法很难产生冲突，一般情况下上述 hash 算法完全可以出现在题目的标准答案中。我们还可以多取一些恰当的 BASE 和 MOD 的值（例如大质数），多进行几组 hash 运算，当结果都相同时才认为原字符串相等，就更加难以构造出使这个 hash 产生错误的数据。
class Solution:
def longestPrefix(self, s: str) -> str:
for i in range(1, len(s)):
if s[:-i] == s[i:]:
return s[i:]
return ''
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) using KMP or rolling hash, where n is the string length. Space complexity is O(n) for LPS array or O(1) extra for rolling hash with modular arithmetic. Verification steps do not increase asymptotic complexity but add constant time per candidate. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Will you consider overlaps between prefix and suffix?
- question_mark
Can you implement this in linear time without extra string copies?
- question_mark
Are you handling hash collisions correctly when using rolling hash?
常见陷阱
外企场景- error
Forgetting that the prefix cannot be the entire string itself.
- error
Miscomputing prefix and suffix hashes leading to false matches.
- error
Failing to account for overlapping prefix and suffix when choosing the longest match.
进阶变体
外企场景- arrow_right_alt
Return the count of all happy prefixes instead of the longest one.
- arrow_right_alt
Modify for a string with uppercase and lowercase letters, requiring case-sensitive matching.
- arrow_right_alt
Determine all indices where a prefix matches a suffix throughout the string.