LeetCode 1062: Longest Repeating Substring Solution

Master LeetCode problem 1062 (Longest Repeating Substring), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1062. Longest Repeating Substring

Medium

String Binary Search Dynamic Programming Rolling Hash Suffix Array Hash Function

Problem Explanation

Explanation:

To solve this problem, we can use binary search along with the Rabin-Karp algorithm. The idea is to search for the longest repeating substring of length len in the given string. We can use the Rabin-Karp algorithm to efficiently check if there exists a repeating substring of length len in the string.

We start with a binary search on the possible lengths of the repeating substring. The search space is from 1 to the length of the string.
For each length len we check if there exists a repeating substring of length len using the Rabin-Karp algorithm. If such a substring exists, we update our answer and continue the binary search on the upper half.
The Rabin-Karp algorithm helps us efficiently check if there exists a repeating substring of length len. We calculate the hash of substrings of length len using rolling hash technique. If we find any two substrings with the same hash, we compare the substrings character by character to confirm if they are indeed the same.
We keep track of the longest repeating substring found so far and return it as the result.

Solution Code

class Solution {
    public int longestRepeatingSubstring(String S) {
        int left = 1, right = S.length();
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (search(mid, S) != -1) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left - 1;
    }

    private int search(int len, String S) {
        Set<Long> seen = new HashSet<>();
        long base = 26;
        long hash = 0;
        long mod = (long) Math.pow(2, 24);

        for (int i = 0; i < len; i++) {
            hash = (hash * base + (S.charAt(i) - 'a')) % mod;
        }
        seen.add(hash);

        long pow = 1;
        for (int i = 1; i < len; i++) {
            pow = (pow * base) % mod;
        }

        for (int i = 1; i + len <= S.length(); i++) {
            hash = (hash * base - (S.charAt(i - 1) - 'a') * pow + (S.charAt(i + len - 1) - 'a')) % mod;
            if (hash < 0) {
                hash += mod;
            }
            if (seen.contains(hash)) {
                return i;
            }
            seen.add(hash);
        }
        return -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1062 (Longest Repeating Substring)?

This page provides optimized solutions for LeetCode problem 1062 (Longest Repeating Substring) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1062 (Longest Repeating Substring)?

The time complexity for LeetCode 1062 (Longest Repeating Substring) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1062 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1062 in Java, C++, or Python.

Back to LeetCode Solutions