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;
}
}