How does binary search help in solving the Longest Duplicate Substring problem?

Binary search helps by narrowing down the possible substring lengths, enabling an efficient search for the longest valid duplicate substring.

What is the role of rolling hash in this problem?

Rolling hash helps efficiently compute hash values for substrings, allowing for constant-time comparison as the sliding window moves across the string.

How does the sliding window technique optimize substring search?

The sliding window technique ensures that substrings are checked only once as it moves across the string, reducing redundant computations.

Can this problem be solved without binary search?

Yes, but it would require a brute force approach, which is less efficient and not scalable for larger strings.

What is the time complexity of the optimal solution for this problem?

The time complexity is O(n log n), where n is the length of the string, due to binary search combined with efficient substring checks using rolling hash.

#1044

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

最长重复子串

给你一个字符串 s ，考虑其所有重复子串：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。返回任意一个可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。示例 1：输入： s = "banana" 输出： "ana" 示例 2：输…

字符串二分查找滑动窗口滚动哈希后缀数组

题目描述

给你一个字符串 s ，考虑其所有 重复子串 ：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

示例 1：

输入：s = "banana"
输出："ana"

示例 2：

输入：s = "abcd"
输出：""

提示：

2 <= s.length <= 3 * 10⁴
s 由小写英文字母组成

lightbulb

解题思路

方法一：字符串哈希 + 二分查找

字符串哈希是把一个任意长度的字符串映射成一个非负整数，并且其冲突的概率几乎为 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 产生错误的数据。

对于本题，二分枚举长度，找到满足条件的最大长度即可。

时间复杂度 $O(n\log n)$ 。其中 $n$ 为字符串长度。

相似题目：

1062. 最长重复子串

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

class Solution:
    def longestDupSubstring(self, s: str) -> str:
        def check(l):
            vis = set()
            for i in range(n - l + 1):
                t = s[i : i + l]
                if t in vis:
                    return t
                vis.add(t)
            return ''

        n = len(s)
        left, right = 0, n
        ans = ''
        while left < right:
            mid = (left + right + 1) >> 1
            t = check(mid)
            ans = t or ans
            if t:
                left = mid
            else:
                right = mid - 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate explain the trade-offs of binary search in terms of string length?
question_mark
Is the candidate able to effectively implement a rolling hash function?
question_mark
Can the candidate describe the sliding window technique for substring comparison?

warning

常见陷阱

外企场景

error
Not efficiently using the sliding window technique, resulting in excessive comparisons.
error
Incorrectly handling edge cases where no substring is repeated.
error
Misapplying the binary search method and not considering the valid substring space properly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implement the solution without binary search, using brute force for substring comparison.
arrow_right_alt
Consider using different hashing techniques such as polynomial rolling hashes.
arrow_right_alt
Optimize for extremely large input sizes, exploring parallelization strategies.

help

常见问题

外企场景

继续练习

#2223 构造字符串的总得分和 #718 最长重复子数组 #187 重复的DNA序列