LeetCode: Longest Repeating Substring

Posted on August 8, 2019July 26, 2020 by braindenny

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: Binary search by a substring length

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

func longestRepeatingSubstring(S string) int {
    left, right := 1, len(S)
    // T, T, T, F, F
    // Find the first false and keep updating the result
    for left < right {
        mid := (right-left)/2 + left
        if hasDuplicate(S, mid) {
            left = mid+1
        } else {
            right = mid
        }
    }
    return left-1
}

Solution: Binary search by a substring length

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

func longestRepeatingSubstring(S string) int {
    res := 0
    left, right := 1, len(S)
    // T, T, T, F, F
    // Find the first false and keep updating the result
    for left < right {
        mid := (right-left)/2 + left
        if hasDuplicate(S, mid) {
            // right half
            if mid > res {
                res = mid
            }
            left = mid+1
        } else {
            right = mid
        }
    }
    return res
}

Solution:

// 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^2)
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
}

Post Views: 0