1062

1062. Longest Repeating Substring (Medium)

Given a string s, return the length of the longest repeating substrings. If no repeating substring exists, return 0.

 

Example 1:

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

Example 2:

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

Example 3:

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

 

Constraints:

• 1 <= s.length <= 2000
• s consists of lowercase English letters.

Companies:
VMware

Related Topics:
String, Binary Search, Dynamic Programming, Rolling Hash, Suffix Array, Hash Function

Solution 1. Rabin Karp + Binary Search

// OJ: https://leetcode.com/problems/longest-repeating-substring/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
    int longestRepeatingSubstring(string s) {
        int L = 1, R = s.size();
        auto valid = [&](int len) {
            unordered_set<unsigned> seen;
            unsigned h = 0, N = s.size(), p = 1, d = 16777619;
            for (int i = 0; i < N; ++i) {
                h = h * d + s[i];
                if (i < len) p *= d;
                else h -= p * s[i - len];
                if (i >= len - 1) {
                    if (seen.count(h)) return true;
                    seen.insert(h);
                }
            }
            return false;
        };
        while (L <= R) {
            int M = (L + R) / 2;
            if (valid(M)) L = M + 1;
            else R = M - 1;
        }
        return R;
    }
};