Welcome to Subscribe On Youtube

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
• Go

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

All Problems

All Solutions