Longest Repeating Substring

Problem

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

Examples

Example 1:

1
2
3


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

Example 2:

1
2
3


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

Example 3:

1
2
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.

Solution

Method 1 – Binary Search with Rolling Hash

Intuition

To find the longest repeating substring, we can use binary search on the substring length and check for duplicates using a rolling hash (Rabin-Karp). This efficiently narrows down the maximum length by checking if any substring of a given length repeats.

Approach

Set left and right pointers for binary search on substring length (from 1 to n-1).
For each length mid, use a rolling hash to check if any substring of that length repeats:
- Compute hash for the first substring of length mid.
- Slide the window, updating the hash in O(1) time, and check for duplicates using a set.
If a duplicate is found, move left up; otherwise, move right down.
Return the maximum length found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
public:
    int longestRepeatingSubstring(string s) {
        int n = s.size(), l = 1, r = n, ans = 0;
        while (l <= r) {
            int m = (l + r) / 2;
            unordered_set<long long> seen;
            long long h = 0, a = 26, mod = 1e9+7, pow = 1;
            for (int i = 0; i < m; ++i) h = (h * a + s[i] - 'a') % mod, pow = (pow * a) % mod;
            seen.insert(h);
            bool found = false;
            for (int i = m; i < n; ++i) {
                h = (h * a - (s[i-m] - 'a') * pow % mod + mod) % mod;
                h = (h + s[i] - 'a') % mod;
                if (seen.count(h)) { found = true; break; }
                seen.insert(h);
            }
            if (found) ans = m, l = m + 1;
            else r = m - 1;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


func longestRepeatingSubstring(s string) int {
    n := len(s)
    l, r, ans := 1, n, 0
    for l <= r {
        m := (l + r) / 2
        seen := map[int64]struct{}{}
        var h, a, mod, pow int64 = 0, 26, 1e9+7, 1
        for i := 0; i < m; i++ {
            h = (h*a + int64(s[i]-'a')) % mod
            pow = (pow * a) % mod
        }
        seen[h] = struct{}{}
        found := false
        for i := m; i < n; i++ {
            h = (h*a - int64(s[i-m]-'a')*pow%mod + mod) % mod
            h = (h + int64(s[i]-'a')) % mod
            if _, ok := seen[h]; ok {
                found = true
                break
            }
            seen[h] = struct{}{}
        }
        if found {
            ans = m
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    public int longestRepeatingSubstring(String s) {
        int n = s.length(), l = 1, r = n, ans = 0;
        while (l <= r) {
            int m = (l + r) / 2;
            Set<Long> seen = new HashSet<>();
            long h = 0, a = 26, mod = 1000000007, pow = 1;
            for (int i = 0; i < m; ++i) {
                h = (h * a + s.charAt(i) - 'a') % mod;
                pow = (pow * a) % mod;
            }
            seen.add(h);
            boolean found = false;
            for (int i = m; i < n; ++i) {
                h = (h * a - (s.charAt(i-m) - 'a') * pow % mod + mod) % mod;
                h = (h + s.charAt(i) - 'a') % mod;
                if (seen.contains(h)) { found = true; break; }
                seen.add(h);
            }
            if (found) { ans = m; l = m + 1; }
            else r = m - 1;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


class Solution {
    fun longestRepeatingSubstring(s: String): Int {
        val n = s.length
        var l = 1
        var r = n
        var ans = 0
        while (l <= r) {
            val m = (l + r) / 2
            val seen = mutableSetOf<Long>()
            var h = 0L
            val a = 26L
            val mod = 1_000_000_007L
            var pow = 1L
            for (i in 0 until m) {
                h = (h * a + (s[i] - 'a')) % mod
                pow = (pow * a) % mod
            }
            seen.add(h)
            var found = false
            for (i in m until n) {
                h = (h * a - (s[i-m] - 'a') * pow % mod + mod) % mod
                h = (h + (s[i] - 'a')) % mod
                if (h in seen) { found = true; break }
                seen.add(h)
            }
            if (found) {
                ans = m
                l = m + 1
            } else {
                r = m - 1
            }
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution:
    def longestRepeatingSubstring(self, s: str) -> int:
        n = len(s)
        l, r, ans = 1, n, 0
        a, mod = 26, 10**9+7
        while l <= r:
            m = (l + r) // 2
            h, pow_a = 0, 1
            seen = set()
            for i in range(m):
                h = (h * a + ord(s[i]) - ord('a')) % mod
                pow_a = (pow_a * a) % mod
            seen.add(h)
            found = False
            for i in range(m, n):
                h = (h * a - (ord(s[i-m]) - ord('a')) * pow_a % mod + mod) % mod
                h = (h + ord(s[i]) - ord('a')) % mod
                if h in seen:
                    found = True
                    break
                seen.add(h)
            if found:
                ans = m
                l = m + 1
            else:
                r = m - 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


impl Solution {
    pub fn longest_repeating_substring(s: String) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let (mut l, mut r, mut ans) = (1, n, 0);
        while l <= r {
            let m = (l + r) / 2;
            let mut seen = std::collections::HashSet::new();
            let (mut h, a, mod_, mut pow) = (0u64, 26u64, 1_000_000_007u64, 1u64);
            for i in 0..m {
                h = (h * a + (s[i] - b'a') as u64) % mod_;
                pow = (pow * a) % mod_;
            }
            seen.insert(h);
            let mut found = false;
            for i in m..n {
                h = (h * a + (s[i] - b'a') as u64) % mod_;
                h = (h + mod_ - ((s[i-m] - b'a') as u64 * pow % mod_)) % mod_;
                if seen.contains(&h) {
                    found = true;
                    break;
                }
                seen.insert(h);
            }
            if found {
                ans = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        ans as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
    longestRepeatingSubstring(s: string): number {
        const n = s.length;
        let l = 1, r = n, ans = 0;
        const a = 26, mod = 1e9+7;
        while (l <= r) {
            const m = Math.floor((l + r) / 2);
            let h = 0, pow = 1;
            const seen = new Set<number>();
            for (let i = 0; i < m; ++i) {
                h = (h * a + s.charCodeAt(i) - 97) % mod;
                pow = (pow * a) % mod;
            }
            seen.add(h);
            let found = false;
            for (let i = m; i < n; ++i) {
                h = (h * a - (s.charCodeAt(i-m) - 97) * pow % mod + mod) % mod;
                h = (h + s.charCodeAt(i) - 97) % mod;
                if (seen.has(h)) { found = true; break; }
                seen.add(h);
            }
            if (found) { ans = m; l = m + 1; }
            else r = m - 1;
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n log n), as we binary search over substring length and check all substrings of a given length.
🧺 Space complexity: O(n), for the hash set storing substring hashes.

Problem#

Examples#

Solution#

Method 1 – Binary Search with Rolling Hash#

Intuition#

Approach#

Code#

Complexity#