longest-repeating-substring

< Previous 　　　　　　　　　　　　　　　　 Next >

1062. Longest Repeating Substring (Medium)

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

Related Topics

[String] [Binary Search] [Dynamic Programming] [Suffix Array] [Hash Function] [Rolling Hash]

Hints

Hint 1

Generate all substrings in O(N^2) time with hashing.

Hint 2

Choose those hashing of strings with the largest length.