# Leetcode – Maximum Repeating Substring Solution

String manipulation is a fundamental topic in computer science, and a popular subject for technical interviews. The problem “Maximum Repeating Substring” from Leetcode serves as a hands-on exercise to strengthen one’s understanding of string operations. This article aims to offer a comprehensive guide to solving this problem using Python, detailing different approaches, their complexities, and how to optimize them.

## Problem Statement

Given a string sequence and a string word, the task is to find the maximum k, for which the word can be repeated k times to form a substring of sequence.

For instance,

sequence = "ababc", word = "ab"

Here, the output should be 2 because “ab” can be repeated two times consecutively to form a substring in “ababc”.

## Brute-Force Approach: Iterative String Concatenation and Checking

The most naive way to solve this problem is to iteratively build a string by repeating the word and then check if it is a substring of the sequence.

#### Python Code

def maxRepeating(sequence, word):
count = 0
temp_word = word
while temp_word in sequence:
count += 1
temp_word += word
return count

### Time Complexity

The time complexity for this approach can be approximately O(n^2), where n is the length of the sequence. This is because for every iteration, we are checking if the concatenated string temp_word is a substring of sequence, which itself is an O(n) operation.

## Optimized Approach: Sliding Window

An optimized approach is to use the sliding window technique to check for repeated instances of word in sequence.

#### Python Code

def maxRepeating(sequence, word):
len_seq, len_word = len(sequence), len(word)
count, max_count = 0, 0

for i in range(len_seq - len_word + 1):
if sequence[i:i + len_word] == word:
j = i
while sequence[j:j + len_word] == word:
count += 1
j += len_word
max_count = max(max_count, count)
count = 0
return max_count

### Time Complexity

The time complexity for this approach is O(n×m), where n is the length of sequence and m is the length of word.

## Edge Cases

### Case 1: Empty Strings

The sequence or word can be empty, in which case, the maximum repeating count is zero.

sequence = ""
word = "abc"

The output should be 0.

### Case 2: Single Character Words

The word could be a single character, and in such cases, the count would be the number of consecutive repetitions of that character.

sequence = "aaaaa"
word = "a"

The output should be 5.

assert maxRepeating("ababc", "ab") == 2
assert maxRepeating("abababa", "aba") == 1