Maximum Repeating Substring

Problem Description

Given strings sequence and word, return the maximum k-repeating value of word in sequence. A string word is k-repeating if word concatenated k times is a substring of sequence. If word is not a substring of sequence, the maximum k-repeating value is 0.

Key Insights

• The problem requires finding how many times a substring can be repeated and still be found within a larger string.
• A simple approach involves concatenating the word multiple times and checking for its presence in the sequence.
• The maximum k value can be determined by incrementing k until the concatenated word is no longer a substring of the sequence.

Space and Time Complexity

Time Complexity: O(n * m), where n is the length of sequence and m is the maximum number of repetitions of word checked. Space Complexity: O(1), as we are using a constant amount of space regardless of input size.

Solution

To solve the problem, we can use a loop to repeatedly concatenate the word and check if this new string is a substring of sequence. We will keep track of the maximum value of k where this condition holds true. We check for the presence of the concatenated string in the original sequence using a built-in substring search method.

Code Solutions