1044. Longest Duplicate Substring

题目信息

题号:

1044

难度:

Hard

主题:

字符串、重复子串、最长长度

原题:

LeetCode 1044

重点:

相同连续子串必须在 s 中至少出现两次,两个出现区间允许重叠;最长答案不唯一时可返回任意一个

题目重述

给定只包含小写英文字母的字符串 s。寻找一个非空连续子串,使相同文本能在 s 中找到至少两个不同的起始位置。两个出现区间可以共享部分下标。

请返回长度最大的重复子串。若有多个不同文本具有相同的最大长度,可以返回其中任意一个;若不存在非空重复子串,返回空字符串。

2 <= s.length <= 3 * 10^4,s 只包含小写英文字母。

自建示例

重复子串在不同位置出现:

输入:s = "mississippi"
输出:"issi"
解释:"issi" 分别从下标 1 和 4 开始出现,长度为 4;不存在更长的重复连续子串。

不存在任何重复字符:

输入:s = "ab"
输出:""
解释:两个长度为 1 的子串分别是 a 和 b,没有非空文本出现两次。