[Leetcode][1044. 最长重复子串] 3种方法:从暴力到二分,二分搜索 + 字符串哈希,后缀数组

By Long Luo

Leetcode 1044. 最长重复子串 题目如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1044. 最长重复子串

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

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


示例 1:
输入:s = "banana"
输出:"ana"

示例 2:
输入:s = "abcd"
输出:""


提示:
2 <= s.length <= 3 * 10^4
s由小写英文字母组成

这是一道Hard难度的题,我们将展示这道题的几种解决方法:

方法一:从暴力到二分

思路与算法:

首先想到的是暴力法,用一个哈希表存储每个字母的出现次数,那么答案字符串的首字母至少出现 \(2\) 次,中间字符至少出现一次。

  1. 第一层循环 \(0 < i < len - 1\),遍历整个字符串;
  2. 第二层循环,子字符串长度,\(i < j < len - i\)
  3. 第三层循环,判断第二层循环的字符串在后续字符串中是否出现。

于是写出了下列Ver 1的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public String longestDupSubstring(String s) {
if (s == null || s.length() <= 1) {
return "";
}

Map<Character, Integer> freq = new HashMap<>();
for (char ch : s.toCharArray()) {
freq.put(ch, freq.getOrDefault(ch, 0) + 1);
}
StringBuilder sb = new StringBuilder();
int len = s.length();
int maxLen = 0;
String ans = "";
for (int i = 0; i < len; i++) {
sb.delete(0, sb.length());
char ch = s.charAt(i);
if (freq.getOrDefault(ch, 0) <= 1) {
continue;
}
for (int j = i; j < len - sb.length(); j++) {
sb.append(s.charAt(j));
for (int k = i + 1; k < len; k++) {
String str = s.substring(k, len);
if (str.contains(sb.toString())) {
if (sb.length() >= maxLen) {
ans = sb.toString();
}
maxLen = Math.max(maxLen, sb.length());
break;
}
}
}
}

return ans;
}

上述代码,时间复杂度为 \(O(n^4)\),会超时

通过观察,发现Ver 1代码有很多改进地方,于是更新到Ver 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// BF Opt time: O(n^3) space: O(n)
// Timeout
public static String longestDupSubstring_bf_opt(String s) {
int len = s.length();
int[] cnt = new int[26];
for (char ch : s.toCharArray()) {
cnt[ch - 'a']++;
}

int maxLen = 0;
String ans = "";
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len - 1; i++) {
char ch = s.charAt(i);
if (cnt[ch - 'a'] <= 1) {
continue;
}

for (int segLen = len - i; segLen > maxLen; segLen--) {
sb.delete(0, sb.length());
sb.append(s, i, i + segLen);
String str = s.substring(i + 1, len);
if (str.contains(sb.toString()) && sb.length() > maxLen) {
ans = sb.toString();
maxLen = Math.max(maxLen, sb.length());
break;
}
}
}

return ans;
}

Ver 2时间复杂度降低到 \(O(n^3)\),但仍然会超时,所以还需要优化!

很明显,题目要求的子字符串的长度范围为 \([0, n - 1]\),那么枚举每个位置作为起点,二分搜索以找到最大长度,于是有了下面的Ver 3代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// Binary Search time: O(n^2logn) space: O(n)
// TimeOut
public static String longestDupSubstring_bs(String s) {
int len = s.length();
int[] cnt = new int[26];
for (char ch : s.toCharArray()) {
cnt[ch - 'a']++;
}

String ans = "";
int maxLen = 0;

for (int i = 0; i < len; i++) {
if (cnt[s.charAt(i) - 'a'] < 2) {
continue;
}

int ret = binarySearch(s, i, maxLen + 1, len - 1 - i);
if (ret > maxLen) {
maxLen = ret;
ans = s.substring(i, i + maxLen);
}
}

return ans;
}

public static int binarySearch(String s, int idx, int left, int right) {
int ans = 0;

while (left <= right) {
int mid = left + (right - left) / 2;
String subStr = s.substring(idx, idx + mid);
String rightSubStr = s.substring(idx + 1);
if (rightSubStr.contains(subStr)) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}

return ans;
}

复杂度分析

  • 时间复杂度:\(O(n^2logn)\),其中 \(n\) 为字符串长度。

  • 空间复杂度:\(O(n)\)。哈希表和字符串均需要存储 \(n\) 个元素。

方法二:二分搜索 + 字符串Hash

思路与算法:

方法一代码会超时,我们需要寻求更加高效的解法。

通过看别人的题解,终于知道咋做了,方法是 Rabin-Karp 字符串编码 。浅显易懂的题解在 字符串哈希

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public String longestDupSubstring(String s) {
String ans = "";
int len = s.length();
int left = 0;
int right = len - 1;
while (left <= right) {
int mid = left + (right - left + 1) / 2;
String ret = searchWin(s, mid);
if (ret.length() > 0) {
left = mid + 1;
ans = ret;
} else {
right = mid - 1;
}
}

return ans;
}

public String searchWin(String s, int len) {
int PRIME = 31;
Set<Long> seen = new HashSet<>();
long hash = 0;
long power = 1;
for (int i = 0; i < len; i++) {
hash = PRIME * hash + s.charAt(i);
power *= PRIME;
}

seen.add(hash);

for (int i = len; i < s.length(); i++) {
hash = PRIME * hash + s.charAt(i) - power * s.charAt(i - len);
String subStr = s.substring(i - len + 1, i + 1);
if (seen.contains(hash) && s.indexOf(subStr) != i) {
return subStr;
}

seen.add(hash);
}

return "";
}

复杂度分析

  • 时间复杂度:\(O(nlogn)\),其中 \(n\) 为字符串长度。

  • 空间复杂度:\(O(n)\)

方法三:后缀数组

看题解发现还有后缀数组的解法,待学有余力时再来看看:

题解如下:

  1. 一题双解 :「字符串哈希 + 二分」&「后缀数组」

  2. O(n) 复杂度的后缀数组解法


All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗