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

All Problems

All Solutions