文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定字符串 S，找出最長重復子串的長度。如果不存在重復子串就返回 0。

示例 1： 輸入："abcd" 輸出：0 解釋：沒有重復子串。示例 2： 輸入："abbaba" 輸出：2 解釋：最長的重復子串為 "ab" 和 "ba"，每個出現 2 次。示例 3： 輸入："aabcaabdaab" 輸出：3 解釋：最長的重復子串為 "aab"，出現 3 次。示例 4： 輸入："aaaaa" 輸出：4 解釋：最長的重復子串為 "aaaa"，出現 2 次。提示： 字符串 S 僅包含從 'a' 到 'z' 的小寫英文字母。 1 <= S.length <= 1500

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-repeating-substring
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：
LeetCode 875. 愛吃香蕉的珂珂（二分查找）
LeetCode LCP 12. 小張刷題計劃（二分查找）
LeetCode 1011. 在 D 天內送達包裹的能力（二分查找）
LeetCode 5438. 制作 m 束花所需的最少天數（二分查找）

• 直接二分查找重復子串的長度，檢查是否存在重復子串

class Solution { public:int longestRepeatingSubstring(string S) {int l = 0, r = S.size()-1, len, maxlen;while(l <= r){len = l+((r-l)>>1);if(haveRepeat(S, len))maxlen = len, l = len+1;elser = len-1;}return maxlen;}bool haveRepeat(string& S, int len){unordered_set<string> set;string sub;for(int i = 0; i <= S.size()-len; i++){sub = S.substr(i, len);if(!set.count(sub))set.insert(sub);elsereturn true;//有重復的子串}return false;} };

44 ms 19.3 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1062. 最长重复子串（二分查找）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。