{x}
blog image

Maximum Repeating Substring

For a string sequence, a string word is k-repeating if word concatenated k times is a substring of sequence. The word's maximum k-repeating value is the highest value k where word is k-repeating in sequence. If word is not a substring of sequence, word's maximum k-repeating value is 0.

Given strings sequence and word, return the maximum k-repeating value of word in sequence.

 

Example 1:

Input: sequence = "ababc", word = "ab"
Output: 2
Explanation: "abab" is a substring in "ababc".

Example 2:

Input: sequence = "ababc", word = "ba"
Output: 1
Explanation: "ba" is a substring in "ababc". "baba" is not a substring in "ababc".

Example 3:

Input: sequence = "ababc", word = "ac"
Output: 0
Explanation: "ac" is not a substring in "ababc".

 

Constraints:

  • 1 <= sequence.length <= 100
  • 1 <= word.length <= 100
  • sequence and word contains only lowercase English letters.

Solution Explanation for Maximum Repeating Substring

This problem asks to find the maximum number of times a given word appears consecutively as a substring within a given sequence.

Approach

The most straightforward approach is to iterate through possible repetition counts (k) and check if the word repeated k times is a substring of the sequence. We start with the largest possible k (the integer division of the sequence length by the word length) and decrement until k is 0. If a repeated word is found as a substring, we return k; otherwise, we continue. If no repetition is found, we return 0.

Time and Space Complexity Analysis

Time Complexity: O(m*n), where n is the length of sequence and m is the length of word. In the worst case, the algorithm iterates through all possible values of k and for each k it performs a substring search. The substring search in most languages (like Python's in operator or Java's contains method) has a time complexity that is at most O(mn) where n is the length of sequence and m is the length of repeated word.

Space Complexity: O(m*k), where m is the length of word and k is the maximum repeating value. In the worst case, we might need to construct a string of length m*k for the repeated word. However, this space complexity is often optimized by the underlying string operations which may avoid creating this large repeated string in memory directly. Some implementations might optimize the space used by string operations (e.g., using rolling hash techniques), making the effective space complexity closer to O(m).

Code Explanation (Python)

class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        for k in range(len(sequence) // len(word), -1, -1):
            if word * k in sequence:
                return k
        return 0

The Python code directly implements the described approach. It iterates from the maximum possible k down to 0. The word * k efficiently creates the repeated word string, and the in operator performs the substring check.

Code Explanation (Java)

class Solution {
    public int maxRepeating(String sequence, String word) {
        for (int k = sequence.length() / word.length(); k > 0; --k) {
            if (sequence.contains(word.repeat(k))) {
                return k;
            }
        }
        return 0;
    }
}

The Java code is very similar to the Python version. word.repeat(k) creates the repeated word, and sequence.contains() performs the substring check.

Code Explanation (Other Languages)

The other language examples (C++, Go, TypeScript, Rust, C) follow the same basic algorithm. The specific string manipulation functions might differ slightly depending on the language, but the overall approach remains consistent. Note that some solutions might employ different optimizations internally for substring search, potentially impacting the precise time complexity constants. The Rust solution showcases a dynamic programming approach, which might offer a slight performance advantage for certain cases but still retains the same overall time complexity bounds.