題目
#

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 中。