文章目录
-
- 题目描述
- 思路分析
- 完整代码
题目描述
给你一个字符串 s ，考虑其所有 重复子串 ：即，s 的连续子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。
返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 “” 。
示例 1：
输入：s = “banana”
输出：“ana”
示例 2：
输入：s = “abcd”
输出：""
思路分析
这居然是一道困难题，不过思路还是比较清晰的，题目中有个关键点就是，考虑其所有 重复子串 。这些出现之间可能存在重叠。这句话什么意思呢 打个比方， 比如示例1 中的 banana，可以重叠就是ana 不可重叠就是an。
使用滑动窗口，left维护窗口左端，right维护窗口右端，
查找 s[left:right] 是否在 s[left+1:] 里出现过，
- 如果出现过则判断当前窗口是否是最长的，如果是则更新答案值，然后更新右端指针right，让窗口扩大继续寻找。
- 如果没有出现过，则缩短窗口，让left往后移动一个位置。
上面只是想到的一个解法，可以通过。但是我觉得困难题应该不是让你这么做的。我这个相当于伪暴力？？
不过看了一眼答案区，二分+什么什么编码，，没用过，懒得看了，溜了溜了。。。。
完整代码
class Solution:def longestDupSubstring(self, s: str) -> str:left = 0right = 1res = ''while right < len(s):if s[left:right] in s[left + 1:]:if len(res) < len(s[left:right]):res = s[left:right]right += 1continueleft += 1print(res)return res