Longest Repeating Substring - Leetcode Solution

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

Solution: Approach 1: Brute Force

1. Iterate through all the possible pairs of substrings and check if they are equal.
2. If they are equal, update the maximum length of the repeating substring.
3. Return the maximum length.

Time Complexity: O(n^3) Space Complexity: O(1)

Approach 2: Binary Search + Rabin-Karp Algorithm

1. Find the minimum and maximum length of the substring using binary search.
2. Using the Rabin-Karp algorithm, hash all the substrings of length mid and store them in a hashset.
3. If a substring already exists in the hashset, update the maximum length of the repeating substring.
4. If the maximum length is greater than mid, update the minimum length to mid + 1, else update the maximum length to mid - 1.
5. Repeat steps 2-4 until minimum length is greater than maximum length.
6. Return the maximum length.

Time Complexity: O(n^2 log n) Space Complexity: O(n^2)

Approach 3: Suffix Tree

1. Build a suffix tree from the input string, s.
2. Traverse through the suffix tree and find all the nodes with more than one child.
3. The substring represented by the path from the root to the node with more than one child is a repeating substring.
4. Update the maximum length of the repeating substring.
5. Return the maximum length.

Time Complexity: O(n) Space Complexity: O(n)

Among these three approaches, the most efficient approach is the suffix tree approach, which has a time complexity of O(n) and a space complexity of O(n).

1class Solution {
2public:
3    int longestRepeatingSubstring(string S) {
4        int n = S.length();
5        // Base case
6        if (n == 0 || n == 1) return n;
7 
8        // To store results of subproblems
9        int dp[n][n];
10        memset(dp, 0, sizeof dp);
11 
12        // Iterate over the length of the string
13        for (int len = 2; len <= n; len++) {
14            for (int i = 0; i < n - len + 1; i++) {
15                int j = i + len - 1;
16 
17                if (len == 2 && S[i] == S[j])
18                    dp[i][j] = 2;
19                else if (S[i] == S[j])
20                    dp[i][j] = dp[i + 1][j - 1] + 2;
21                else
22                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
23            }
24        }
25 
26        return dp[0][n - 1];
27    }
28};