We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Repeating Substring

Number: 1764

Difficulty: Easy

Paid? No

Companies: Pure Storage, Asana

Problem Description

Given a string sequence and a string word, determine the maximum integer k such that word repeated k times (i.e., word concatenated with itself k times) is a substring of sequence. If word is not found at all, the answer is 0.

Key Insights

  • The problem asks us to find how many consecutive repetitions of word can be found in sequence.
  • Since the length of sequence and word are small (at most 100 characters), a direct search is efficient.
  • Incrementally build the repeated string (e.g., word, wordword, wordwordword, etc.) until it is no longer a substring of sequence.
  • No complex data structures are needed; simple string concatenation and substring matching are sufficient.

Space and Time Complexity

Time Complexity: O(m * n) where m is the maximum k found (each check involves a substring search over sequence) and n is the length of sequence. In worst-case scenarios with small input sizes, this is efficient. Space Complexity: O(m * |word|) to store the current repeated string, which is minimal given the constraints.

Solution

We iteratively check if the word repeated k times is a substring of sequence. Start from k = 1 and increment k until the concatenated string does not appear in sequence. The last successful k is returned as the maximum repeating value. The primary data structure involved is a string that is built up iteratively, and the algorithmic technique is greedy iterative search with substring matching.

Code Solutions

# Python solution for Maximum Repeating Substring
def maxRepeating(sequence, word):
    # Initialize count with 0
    k = 0
    # Current repeated string starts empty
    repeated = ""
    # Loop until adding one more word makes repeated not a substring of sequence
    while True:
        # Append word for the next repetition
        repeated += word
        # Check if the current repeated string is present in sequence
        if repeated in sequence:
            # Valid repetition, increment the count
            k += 1
        else:
            # If not present, break out of the loop
            break
    # Return the maximum k such that word repeated k times is a substring of sequence
    return k

# Example usage:
print(maxRepeating("ababc", "ab"))  # Expected output: 2
← Back to All Questions