題目#
leetcode 1062 - Longest Repeating Substring(題目說明請點連結)
題目簡述#
給定一個字串，找到最長的重複子字串的長度。重複子字串是指在字串中出現至少兩次的子字串。
Example 1:
Input: "abcd"
Output: 0
Explanation: 沒有重複的子字串。Example 2:
Input: "abbaba"
Output: 2
Explanation: 最長的重複子字串是 "ab" 和 "ba"，每個都出現兩次。Example 3:
Input: "aabcaabdaab"
Output: 3
Explanation: 最長的重複子字串是 "aab"，出現了 3 次。Example 4:
Input: "aaaaa"
Output: 4
Explanation: 最長的重複子字串是 "aaaa"，出現了兩次。解題思路#
輸入為一個字串，輸出為字串內重複最多的子字串的次數。
這題的思路可以利用有序區間和單調性特性：
假設輸入字符串為 S = “aabcaabdaab”，我們嘗試檢查不同的子串長度是否有重複。
子串長度和重複性： 子串長度 𝐿 (aabcaabdaab)
L 是否有重複子串 重複部分 1 有 單字符如 “a” 重複多次 2 有 如 “aa” 或 “ab” 重複 3 有 如 “aab” 重複 4 無 沒有重複長度 4 的子串 5 無 沒有重複長度 5 的子串 6 無 沒有重複長度 6 的子串 有序區間：從 1 到 6（子串長度）是有序的，因為是否有重複子串隨著長度變化而遵守規律。
單調性：
當 𝐿≤3 時，存在重複子串。
當 L≥4 時，不存在重複子串。
透過 Binary search 在這個有序陣列當中找到最大重複的那個數字，
並寫另外寫一個方法用HashSet來判斷是否有重複值。
例子說明#
s = "aabcaabdaab"
- 初始情況：
left = 1，right = 11
第一次二分：
mid = 6- 檢查長度 6 的子串是否有重複
- 沒有重複，
right = mid - 1 = 5
第二次二分：
mid = 3- 檢查長度 3 的子串是否有重複
- “aab” 重複 3 次，有重複，
left = mid = 3
第三次二分：
mid = 4- 檢查長度 4 的子串是否有重複
- 沒有重複，
right = mid - 1 = 3
最終結果：
left = 3，返回 3
完整程式碼#
java
class Solution {
public int longestRepeatingSubstring(String s) {
int left = 1, right = s.length(); // 初始化二分搜索的範圍
while(left < right) { // 當left小於right時繼續搜索
int mid = left + (right - left + 1) / 2; // 計算中間值，使用上取整
if(hasRepeatingSubstring(s, mid)) { // 檢查是否有長度為mid的重複子串
left = mid; // 如果有重複，嘗試更大的長度
} else {
right = mid - 1; // 如果沒有重複，嘗試更小的長度
}
}
return left; // 返回最長重複子串的長度
}
public boolean hasRepeatingSubstring(String s, int length) {
HashSet<String> set = new HashSet<>(); // 創建HashSet來存儲子串
for (int i = 0; i <= s.length() - length; i++) { // 遍歷所有可能的起始位置
if(set.contains(s.substring(i, i + length))) { // 檢查當前子串是否已經存在
return true; // 如果存在，說明有重複
} else {
set.add(s.substring(i, i + length)); // 將當前子串加入集合
}
}
return false; // 沒有找到重複子串
}
}時間複雜度#
時間複雜度：O(n² log n)，其中 n 是字串的長度。
- 最佳情況：若字串中很快就找到重複子串，則每次二分時 hasRepeatingSubstring 很快返回，實際遍歷的子串較少，接近 O(n log n)。
- 最差情況：每次都要完整檢查所有長度為 mid 的子串，且二分 log n 次，每次檢查 O(n) 個子串，每個子串長度 O(n)，所以總體為 O(n² log n)。
空間複雜度：O(n²)，用於存儲所有可能的子串於 HashSet 中。