Problem Description

You are given two strings: sequence and word. Your task is to find how many times you can repeat the word consecutively such that the resulting string appears as a substring within sequence.

A string word is considered k-repeating if when you concatenate word exactly k times, the result can be found as a substring in sequence. For example, if word = "ab" and k = 3, then word * k = "ababab". If this appears in sequence, then word is 3-repeating.

The maximum k-repeating value is the largest value of k for which word * k appears as a substring in sequence. If word itself doesn't appear in sequence at all, then the maximum k-repeating value is 0.

The solution works by starting from the maximum possible value of k (which is len(sequence) // len(word) since we can't fit more repetitions than this) and checking downward. For each value of k, it checks if word * k exists as a substring in sequence. The first k value where this condition is true is the maximum k-repeating value, since we're checking from largest to smallest.

For example:

• If sequence = "ababc" and word = "ab", then word * 2 = "abab" is in sequence, but word * 3 = "ababab" is not. So the maximum k-repeating value is 2.
• If sequence = "aaabaaaab" and word = "aaa", then word * 2 = "aaaaaa" is not in sequence, but word * 1 = "aaa" is. So the maximum k-repeating value is 1.

Intuition

The key insight is that if word can be repeated k times and found in sequence, then it can also be repeated k-1, k-2, ... , 1 times and found in sequence. This is because if a longer concatenated string exists as a substring, then any shorter version of it (with fewer repetitions) must also exist within that same substring.

For example, if "ababab" (which is "ab" * 3) exists in the sequence, then "abab" ("ab" * 2) and "ab" ("ab" * 1) must also exist, since they are contained within "ababab".

This monotonic property means we want to find the largest k value that works. We could approach this in two ways:

1. Start from k = 1 and keep increasing until we find a k where word * k is no longer in sequence
2. Start from the maximum possible k and work our way down until we find one that works

The second approach is more efficient because:

• The maximum possible value of k is bounded by len(sequence) // len(word) (we can't fit more repetitions than the sequence length allows)
• We can stop as soon as we find the first working k value when searching from largest to smallest
• Python's substring checking (in operator) is highly optimized, making the check word * k in sequence very fast

By starting from the maximum possible k and checking downward, we guarantee finding the maximum k-repeating value with the fewest checks possible in the best case scenarios.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation uses a straightforward brute-force approach with an optimization to search from the maximum possible value downward.

Algorithm Steps:

1. Calculate the maximum possible k value: len(sequence) // len(word)

   • This represents the theoretical maximum number of times word could fit in sequence
   • For example, if sequence has length 10 and word has length 3, the maximum possible k is 10 // 3 = 3

2. Iterate from maximum k down to 0: Use a reverse range range(len(sequence) // len(word), -1, -1)

   • Starting from the largest possible value ensures we find the maximum k-repeating value first
   • The range includes 0 to handle the case where word doesn't appear in sequence at all

3. Check if word * k exists in sequence: For each k value, concatenate word k times using Python's string multiplication (word * k) and check if it's a substring of sequence using the in operator

   • Python's in operator performs efficient substring matching
   • String multiplication word * k creates the concatenated string in O(k × len(word)) time

4. Return immediately upon finding a match: Since we're checking from largest to smallest, the first k that satisfies the condition is our answer

Time Complexity Analysis:

• Let n = len(sequence) and m = len(word)
• Maximum iterations: n // m + 1
• Each iteration creates a string of length up to n and performs substring matching in O(n)
• Overall time complexity: O(n²/m) in the worst case

Space Complexity: O(n) for storing the concatenated string word * k at each iteration

The solution leverages Python's built-in string operations for simplicity and relies on the monotonic property that if k-repeating exists, then (k-1)-repeating must also exist, allowing us to find the maximum efficiently by searching from largest to smallest.

Example Walkthrough

Let's walk through the solution with sequence = "aaabaaaab" and word = "aa".

Step 1: Calculate maximum possible k

• len(sequence) = 9, len(word) = 2
• Maximum possible k = 9 // 2 = 4

Step 2: Check from k = 4 down to k = 0

• k = 4: Check if "aa" * 4 = "aaaaaaaa" (8 characters) is in "aaabaaaab"

  • Looking for "aaaaaaaa" in sequence... NOT found ❌

• k = 3: Check if "aa" * 3 = "aaaaaa" (6 characters) is in "aaabaaaab"

  • Looking for "aaaaaa" in sequence... NOT found ❌

• k = 2: Check if "aa" * 2 = "aaaa" (4 characters) is in "aaabaaaab"

  • Looking at positions in sequence:
    • Position 4-7: "aaaa" ✓ FOUND!
  • Return k = 2

The answer is 2 because "aa" repeated twice ("aaaa") appears as a substring starting at index 4 in the sequence.

Note how we stop immediately after finding k = 2 works. We don't need to check k = 1 or k = 0 because we've already found our maximum. If we had started from k = 1 and worked upward, we would have had to check k = 1 (which works), k = 2 (which works), k = 3 (which doesn't work) to confirm that 2 is the maximum - requiring more checks overall.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n * m * k) where n is the length of sequence, m is the length of word, and k is the maximum possible value of repeating which is n // m.

The algorithm iterates from k = n // m down to 0. For each value of k, it:

1. Creates a string word * k which takes O(m * k) time
2. Checks if this string is a substring of sequence using the in operator, which takes O(n * m * k) time in the worst case (the substring search needs to compare up to m * k characters at each of the n positions)

Since we iterate at most n // m + 1 times, the total time complexity is O((n // m) * n * m * k). In the worst case where k ≈ n // m, this simplifies to O(n² * m).

Space Complexity: O(m * k) where k can be at most n // m.

The algorithm creates a temporary string word * k in each iteration, which requires O(m * k) space. The maximum value of k is n // m, so the worst-case space complexity is O(n). The space is not accumulated across iterations since each temporary string is discarded before the next one is created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Overlapping Pattern Misunderstanding

A common misconception is thinking that overlapping occurrences of word should be counted separately. For example, if sequence = "aaaa" and word = "aa", one might incorrectly think the answer is 3 (counting "aa" at positions 0, 1, and 2). However, the problem asks for consecutive repetitions, meaning word * k must appear as a continuous substring. The correct answer is 2 since "aaaa" contains "aa" * 2 = "aaaa" but not "aa" * 3 = "aaaaaa".

Solution: Always remember that we're looking for word repeated k times consecutively as a single substring, not counting overlapping occurrences.

2. Inefficient Bottom-Up Approach

A natural but inefficient approach is to start from k=1 and increment until word * k is no longer found:

k = 0
while word * (k + 1) in sequence:
    k += 1
return k

While this works, it's less efficient when the maximum k is small relative to len(sequence) // len(word).

Solution: The provided top-down approach is generally more efficient as it can terminate early when k is large, avoiding unnecessary string constructions and comparisons for smaller k values.

3. Integer Division Edge Cases

When len(word) > len(sequence), the integer division len(sequence) // len(word) returns 0, which is correct. However, developers might forget to handle this case or might use regular division / instead of integer division //, causing type errors.

Solution: Always use integer division // and ensure the range includes 0 to handle cases where word doesn't appear in sequence at all.

4. Memory Overhead with Large Strings

For very large sequences and small words, creating word * k for large k values can consume significant memory. For instance, if word = "a" and sequence is very long, we might create very large intermediate strings.

Solution: For memory-critical applications, consider using string matching algorithms that don't require full string construction, such as:

def maxRepeating(self, sequence: str, word: str) -> int:
    max_k = len(sequence) // len(word)
    for k in range(max_k, -1, -1):
        # Use string search with calculated length instead of construction
        pattern_length = k * len(word)
        found = False
        for i in range(len(sequence) - pattern_length + 1):
            match = True
            for j in range(pattern_length):
                if sequence[i + j] != word[j % len(word)]:
                    match = False
                    break
            if match:
                found = True
                break
        if found:
            return k
    return 0