最长重复子串

Submission

运行时间: 37 ms

内存: 0.0 MB

class Solution:
    def longestRepeatingSubstring(self, s: str) -> int:
        left = 0
        right = len(s)

        def haveRepetition(mid):
            hSet = set()
            for i in range(len(s) - mid + 1):
                temp = s[i:i+mid]
                if temp in hSet:
                    return True
                hSet.add(temp)
            return False 
        
        while left < right:
            middle = (left + right + 1) // 2
            if haveRepetition(middle):
                left = middle
            else:
                right = middle - 1

        return right

Explain

这个题解采用了二分搜索的方法来寻找最长重复子串的长度。算法的基本思想是，通过二分搜索在可能的子串长度范围内查找，利用一个辅助函数 `haveRepetition` 来检查给定长度 `mid` 的子串是否在字符串 `s` 中重复出现。如果有重复，增大查找范围的下限 `left`；如果没有重复，减小查找范围的上限 `right`。最终，`right` 指向的是最长的重复子串的长度。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def longestRepeatingSubstring(self, s: str) -> int:
        # 初始化二分搜索的左右边界
        left = 0
        right = len(s)

        # 辅助函数，用于检测长度为 mid 的子串是否有重复
        def haveRepetition(mid):
            hSet = set()
            for i in range(len(s) - mid + 1):
                temp = s[i:i+mid]
                if temp in hSet:
                    return True
                hSet.add(temp)
            return False 
        
        # 二分搜索最长重复子串的长度
        while left < right:
            middle = (left + right + 1) // 2
            if haveRepetition(middle):
                left = middle
            else:
                right = middle - 1

        return right

Explore

在二分搜索中，目标是确定可以找到重复子串的最长长度。当`haveRepetition`函数确定存在长度为`mid`的重复子串时，意味着所有小于或等于`mid`的长度都可能有重复子串。因此，为了找到更长的可能重复子串，需要将下限`left`调整为`mid`，从而在更大的长度范围内继续搜索。相反，如果没有重复子串，这表明长度为`mid`及以上的子串都不会重复，所以将上限`right`调整为`mid - 1`，在更小的长度范围内继续寻找。

在`haveRepetition`函数中，通过遍历从0到`len(s) - mid`的所有可能起始位置，并截取长度为`mid`的子串，检查这些子串是否在哈希集合`hSet`中已经存在。如果存在，则表示发现了重复子串；如果不存在，则将该子串加入到集合中。这种方法通过覆盖所有可能的起始位置，确保了不会漏掉任何可能的重复子串。

虽然在理论上，当字符串非常长时，存储大量子串可能会消耗大量内存，但在实际应用中，通常操作系统和编程语言的内存管理机制能够有效地处理这种情况。此外，二分搜索迅速缩小检查长度的范围，减少了需要同时存储的子串数量。如果内存仍是问题，可以考虑使用更高效的数据结构（如滚动哈希）来减少存储需求。

使用`(left + right + 1) // 2`而不是`(left + right) // 2`是为了在二分搜索中防止死循环和确保能够覆盖所有可能的情况。特别是当`left`和`right`非常接近时，`(left + right) // 2`可能会导致`middle`值偏小，从而可能在某些情况下无法正确调整`left`的值，造成死循环。使用`(left + right + 1) // 2`确保`middle`在必要时能够取得更大的值，从而更有效地探索搜索空间。