1668. Maximum Repeating Substring
Model: qwen2.5-coder:14b
Topics: String
FAANG asked: 0
Acceptance rate: 38.7%
Problem Breakdown
The problem asks us to find the maximum number of times a given string word can be concatenated and still appear as a substring within another string sequence. The inputs are two strings: sequence and word. The output is an integer representing the highest value of k where word repeated k times is a substring of sequence. If word does not appear even once, the output should be 0.
Implicit constraints include:
- Both
sequenceandwordcontain only lowercase English letters. - The lengths of both strings are between 1 and 100.
Edge cases to consider:
wordis longer thansequence.worddoes not appear insequence.wordappears multiple times but not consecutively.
Intuition
A brute-force approach would involve checking every possible substring of sequence to see if it matches word repeated k times for increasing values of k. This approach is inefficient because the number of substrings grows quadratically with the length of sequence, and checking each one involves linear time operations.
The key insight is that we can build up the repeated string incrementally and check its presence in sequence at each step. This reduces the number of checks significantly, as we only need to perform substring searches on increasing multiples of word.
Approach
- Initialize a variable
kto 0, which will keep track of the maximum number of timeswordcan be repeated. - Create an empty string
repeated_word. - Use a loop to incrementally build
repeated_wordby appendingwordto it in each iteration. - After building
repeated_word, check if it is a substring ofsequence. - If it is, increment
kand continue the loop. - If it is not, break out of the loop as further repetitions will also not be substrings.
- Return the value of
k.
Complexity Analysis
- Time Complexity: O(n * m), where n is the length of
sequenceand m is the length ofword. This is because in the worst case, we might need to check if a string of length up to n (whenrepeated_wordis just undersequence) is a substring ofsequence. - Space Complexity: O(n), as the largest
repeated_wordcan be is approximately the same length assequence.
Solution
def maxRepeating(sequence: str, word: str) -> int:
k = 0
repeated_word = ""
while True:
repeated_word += word
if sequence.find(repeated_word) != -1:
k += 1
else:
break
return k
Edge Cases Handled
wordis longer thansequence: The loop will terminate immediately because the first concatenation ofworditself cannot be a substring.worddoes not appear insequence: The loop will also terminate immediately after the first iteration since an empty string is trivially a substring, but any non-emptyrepeated_wordwill fail the substring check.wordappears multiple times but not consecutively: The approach inherently checks for consecutive repetitions, so if they are not present, the loop will break early.