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.

Testing Your Solution

Before submitting your solution on LeetCode, you should run it on multiple test cases, including edge cases.

assert maxRepeating("ababc", "ab") == 2
assert maxRepeating("ababc", "ba") == 1
assert maxRepeating("ababc", "ac") == 0
assert maxRepeating("", "ab") == 0
assert maxRepeating("aaaaa", "a") == 5
assert maxRepeating("abababa", "aba") == 1

Conclusion

The “Maximum Repeating Substring” problem is a powerful exercise that tests one’s ability to manipulate strings and understand the intricacies of substrings in Python. Though the problem might appear to have an easy brute-force solution, it provides a good opportunity to implement and understand the sliding window technique, which can be more time-efficient.