Maximum Repeating Substring - Video Solutions

Problem Overview: You are given two strings: sequence and word. The goal is to find the maximum integer k such that word repeated k times (i.e., word * k) appears as a substring of sequence. The challenge is efficiently checking how many times the pattern can repeat consecutively while still remaining inside the larger string.

Approach 1: Brute Force Repetition Check (Time: O(n * m * k), Space: O(1))

The direct strategy repeatedly build the string word * k and check whether it exists inside sequence. Start with k = 1, concatenate word each time, and run a substring search using built-in string matching. Stop when the constructed string is no longer found in sequence. The last valid k is the answer. This approach relies heavily on repeated substring checks and string concatenation, so performance degrades when the sequence becomes large. Still, it is simple to implement and demonstrates a clear understanding of the problem mechanics. The logic mainly involves standard operations from string manipulation and basic substring search.

Approach 2: Binary Search on Repetition Count (Time: O(n log k), Space: O(1))

A more efficient solution treats the answer k as a search space. Instead of checking every repetition count sequentially, apply binary search between 0 and n / m (maximum possible repetitions). For each mid value, construct word repeated mid times and check whether it exists in sequence. If the substring exists, move the search right to test larger values. Otherwise move left. This reduces the number of substring checks from linear to logarithmic. The key insight is that the condition is monotonic: if word * k exists, then all smaller repetitions must also exist. This technique combines ideas from string matching and search optimization to significantly reduce unnecessary checks.

Another way to reason about the problem is through pattern repetition tracking similar to techniques used in dynamic programming string problems. Instead of exploring every substring combination, the algorithm focuses only on valid repetition lengths derived from the pattern itself.

Recommended for interviews: Start by explaining the brute force approach because it clearly models the definition of repeated substrings. Then move to the binary search optimization. Interviewers usually expect you to recognize that the answer space is bounded and monotonic, making binary search a clean improvement. Demonstrating both approaches shows problem understanding first and algorithmic optimization second.