Maximum Repeating Substring

easy string substring search brute force

Problem

A string word is k-repeating in sequence if word concatenated k times is a substring of sequence. The maximum k-repeating value is the largest k for which this holds; if word is not a substring of sequence at all, the answer is 0. Return that maximum value.

Inputsequence = "ababc", word = "ab"

Output2

"abab" (ab twice) appears in "ababc", so k = 2. "ababab" does not, so 2 is the max.

Inputsequence = "ababc", word = "ac"

Output0

"ac" is not a substring of "ababc", so the answer is 0.

sequence (lowercase letters)

word (lowercase letters)

def max_repeating(sequence, word):
    k = 0
    candidate = word
    while candidate in sequence:
        k += 1
        candidate += word
    return k

function maxRepeating(sequence, word) {
  let k = 0;
  let candidate = word;
  while (sequence.includes(candidate)) {
    k += 1;
    candidate += word;
  }
  return k;
}

int maxRepeating(String sequence, String word) {
    int k = 0;
    String candidate = word;
    while (sequence.contains(candidate)) {
        k += 1;
        candidate += word;
    }
    return k;
}

int maxRepeating(string sequence, string word) {
    int k = 0;
    string candidate = word;
    while (sequence.find(candidate) != string::npos) {
        k += 1;
        candidate += word;
    }
    return k;
}

Explanation

The answer is the highest k for which word repeated k times still fits inside sequence. Because a longer repetition always contains every shorter one, the valid values of k form an unbroken run 1, 2, …, K. So we can just try them in increasing order and stop at the first failure.

We keep a growing candidate string that always equals word repeated some number of times. It starts as a single copy of word (the k = 1 trial). Each time the candidate is found inside sequence, we bump k and append one more word to test the next larger repetition.

The loop condition candidate in sequence does the heavy lifting: it asks "does this concatenation appear anywhere as a contiguous block?". The moment it does not, the loop ends and k holds the largest repetition that succeeded.

If even one copy of word is missing from sequence, the very first check fails, the loop body never runs, and we correctly return k = 0.

For sequence = "ababc", word = "ab": "ab" is found (k = 1), "abab" is found (k = 2), "ababab" is not — so the answer is 2.

Time: O(n · K) Space: O(n)