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

1062. Longest Repeating Substring

Level

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;
        }
    };
    
  • print("Todo!")
    

All Problems

All Solutions