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.

• Java
• C++
• Python

• 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