##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1062.html

# 1062. Longest Repeating Substring

Medium

## Description

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:

1. The string S consists of only lowercase English letters from 'a' - 'z'.
2. 1 <= S.length <= 1500

## Solution

Use a trie to find repeating substrings. Starting from each index in S, create a trie. If a node in a trie already exists when trying to create the node, then the node represents a repeating substring, so update the maximum length of the repeating substrings. Finally, return the maximum length.

• class Solution {
public int longestRepeatingSubstring(String S) {
int maxLength = 0;
TrieNode root = new TrieNode();
int length = S.length();
for (int i = 0; i < length; i++) {
TrieNode node = root;
for (int j = i; j < length; j++) {
int index = S.charAt(j) - 'a';
if (node.next[index] != null)
maxLength = Math.max(maxLength, j - i + 1);
else
node.next[index] = new TrieNode();
node = node.next[index];
}
}
return maxLength;
}
}

class TrieNode {
TrieNode[] next;

public TrieNode() {
next = new TrieNode[26];
}
}

• // OJ: https://leetcode.com/problems/longest-repeating-substring/
// 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;
}
};

• class Solution:
def longestRepeatingSubstring(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
ans = 0
for i in range(n):
for j in range(i + 1, n):
if s[i] == s[j]:
dp[i][j] = dp[i - 1][j - 1] + 1 if i else 1
ans = max(ans, dp[i][j])
return ans


• func longestRepeatingSubstring(s string) int {
n := len(s)
dp := make([][]int, n)
for i := range dp {
dp[i] = make([]int, n)
}
ans := 0
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if s[i] == s[j] {
if i == 0 {
dp[i][j] = 1
} else {
dp[i][j] = dp[i-1][j-1] + 1
}
ans = max(ans, dp[i][j])
}
}
}
return ans
}

func max(a, b int) int {
if a > b {
return a
}
return b
}