Domain 1EasyCORE

Maximum Repeating Substring

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#String

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 sequence and word contain only lowercase English letters.
  • The lengths of both strings are between 1 and 100.

Edge cases to consider:

  • word is longer than sequence.
  • word does not appear in sequence.
  • word appears 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

  1. Initialize a variable k to 0, which will keep track of the maximum number of times word can be repeated.
  2. Create an empty string repeated_word.
  3. Use a loop to incrementally build repeated_word by appending word to it in each iteration.
  4. After building repeated_word, check if it is a substring of sequence.
  5. If it is, increment k and continue the loop.
  6. If it is not, break out of the loop as further repetitions will also not be substrings.
  7. Return the value of k.

Complexity Analysis

  • Time Complexity: O(n * m), where n is the length of sequence and m is the length of word. This is because in the worst case, we might need to check if a string of length up to n (when repeated_word is just under sequence) is a substring of sequence.
  • Space Complexity: O(n), as the largest repeated_word can be is approximately the same length as sequence.

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

  • word is longer than sequence: The loop will terminate immediately because the first concatenation of word itself cannot be a substring.
  • word does not appear in sequence: The loop will also terminate immediately after the first iteration since an empty string is trivially a substring, but any non-empty repeated_word will fail the substring check.
  • word appears multiple times but not consecutively: The approach inherently checks for consecutive repetitions, so if they are not present, the loop will break early.