Longest Repeating Substring

Similar Problems:

Given a string S, find out the length of the longest repeating substring(s). Return 0 if no repeating substring exists.

Example 1:

Input: "abcd" Output: 0 Explanation: There is no repeating substring.

Example 2:

Input: "abbaba" Output: 2 Explanation: The longest repeating substrings are "ab" and "ba", each of which occurs twice.

Example 3:

Input: "aabcaabdaab" Output: 3 Explanation: The longest repeating substring is "aab", which occurs 3 times.

Example 4:

Input: "aaaaa" Output: 4 Explanation: The longest repeating substring is "aaaa", which occurs twice.

Note:

- The string S consists of only lowercase English letters from ‘a’ – ‘z’.
- 1 <= S.length <= 1500

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// Blog link: https://code.dennyzhang.com/longest-repeating-substring // Basic Ideas: binary search + hashmap // T T T T F F // Complexity: Time O(n*n*log(n)), Space O(n*n) func longestRepeatingSubstring(S string) int { res := 0 left, right := 1, len(S)-1 for left < right { middle := (right-left)/2 + left m := map[string]bool{} has_duplicate := false for i:=0; i+middle<len(S); i++ { str := S[i:i+middle+1] if m[str] { has_duplicate = true if middle+1 > res { res = middle+1 } break } m[str] = true } if has_duplicate == false { right = middle } else { left = middle+1 } } return res }