Maximum Repeating Substring: Simple String Matching

LeetCode 1668, Maximum Repeating Substring, gives you a string sequence and a string word. A value k is the maximum repeating value if word concatenated k times (written as word * k) is a substring of sequence, but word * (k + 1) is not. Return k. If word never appears in sequence at all, return 0.

Examples:

• sequence = "ababc", word = "ab" returns 2 (because "abab" is in "ababc" but "ababab" is not)
• sequence = "ababc", word = "ba" returns 1 (because "ba" is in "ababc" but "baba" is not)
• sequence = "ababc", word = "ac" returns 0 ("ac" is not in "ababc")

The approach: incrementally build and check

The idea is refreshingly direct. Start with k = 0. Build the string word * 1 and check if it appears in sequence. If it does, try word * 2. Keep incrementing k until word * (k + 1) is no longer a substring of sequence. The last successful k is your answer.

Why does this work? The problem asks for the longest run of consecutive, non-overlapping copies of word that fits inside sequence. By checking word * 1, word * 2, word * 3, and so on, you are directly testing every possible repeating count. The first failure tells you that the previous count was the maximum.

The code

def maxRepeating(sequence: str, word: str) -> int:
    k = 0
    while word * (k + 1) in sequence:
        k += 1
    return k

That is the entire solution. Walk through what happens:

1. Initialize k to 0.
2. Build word * (k + 1). For the first iteration, this is word * 1, which is just word itself.
3. Check if that string is a substring of sequence.
4. If yes, increment k and repeat.
5. If no, stop. The current k is the answer.

The loop naturally handles the case where word never appears: the very first check (word * 1 in sequence) fails, k stays at 0, and you return 0.

Visual walkthrough

Let's trace through the algorithm step by step, building up word * k for each value of k and checking membership.

The algorithm tests three candidates. The first two ("ab" and "abab") are found inside the sequence. The third ("ababab") is too long to fit. The answer is the last successful k, which is 2.

Complexity analysis

The loop runs at most n / m times (you cannot fit more than n / m copies of word inside sequence). Each iteration performs a substring check that takes O(n) time. So the total is O(n * n/m), which simplifies to O(n^2 / m).

For the constraints given (both strings up to length 100), this is extremely fast. You will never notice the difference from a theoretically optimal approach.

Building blocks

This problem is built from two fundamental techniques that show up across many string problems.

Substring membership check

The core operation is checking whether one string is a substring of another. In Python, word in sequence does this in one expression. This same operation appears in problems like Find the Index of the First Occurrence in a String and Rotate String, where the key insight often reduces to a single substring check.

Incremental string construction

You build up a candidate string by repeating a pattern and testing it. This idea of "grow a candidate until it fails" appears in binary search style problems and in string repetition problems like Repeated Substring Pattern. The loop structure is the same: increment, build, test, stop on failure.

Edge cases

Word not in sequence at all. If word does not appear anywhere in sequence, the first check (word * 1 in sequence) fails immediately. The function returns 0. No special handling needed.

Word equals sequence. If sequence and word are identical, then word * 1 == sequence is a substring (it is the whole string), but word * 2 is longer than sequence and cannot be a substring. The function returns 1.

Single character word. If word = "a" and sequence = "aaaa", the loop checks "a", "aa", "aaa", "aaaa", and then "aaaaa" which does not fit. The function returns 4. This is the maximum possible k for a single-character word in a sequence of length n.

Word longer than sequence. If len(word) is greater than len(sequence), then word * 1 is already longer than the sequence. The in check fails, and the function returns 0.

From understanding to recall

This problem feels almost too simple when you read through it. Build a repeated string, check if it is a substring, increment. But the details that matter are the ones that slip: using k + 1 in the while condition (not k), starting k at 0 (not 1), and trusting that the in operator handles all the positional logic for you.

Spaced repetition turns this understanding into recall. You drill the incremental build-and-check loop from scratch at increasing intervals. After a few reps, the while loop with word * (k + 1) in sequence writes itself. When you see a string repetition problem in an interview, you are not reconstructing the logic. You are snapping together a brick you already own.

Related posts

• Find the Index of the First Occurrence in a String - Another easy string problem where substring matching is the core operation
• Repeated Substring Pattern - A string repetition problem that asks whether the entire string is built from repeating a single pattern
• Rotate String - A clever string problem where the solution reduces to a single substring membership check