LeetCode 1668 - Maximum Repeating Substring

This problem asks us to determine how many times a given string word can be repeated consecutively while still appearing

leetcodeeasystringdynamic-programmingstring-matching

LeetCode Problem 1668

Difficulty: 🟢 Easy
Topics: String, Dynamic Programming, String Matching

Solution

Problem Understanding

This problem asks us to determine how many times a given string word can be repeated consecutively while still appearing as a substring inside another string called sequence.

More formally, a string is considered k-repeating if word concatenated k times appears somewhere inside sequence as a contiguous substring. Our goal is to find the largest possible value of k.

For example, if:

sequence = "ababc"
word = "ab"

Then:

  • "ab" appears in "ababc" → k = 1
  • "abab" appears in "ababc" → k = 2
  • "ababab" does not appear → k = 3 is invalid

Therefore, the answer is 2.

The input consists of two strings:

  • sequence, the larger string in which we search
  • word, the repeating unit we want to test

The expected output is a single integer representing the maximum number of consecutive repetitions of word that exist as a substring of sequence.

The constraints are relatively small:

  • sequence.length <= 100
  • word.length <= 100

These limits immediately suggest that we can afford somewhat inefficient operations like repeated substring checks without worrying about performance. Since the total input size is tiny, even algorithms with quadratic or cubic behavior may still pass comfortably.

However, there are still important edge cases to consider.

One tricky case occurs when word does not appear in sequence at all. In this situation, the answer must be 0.

Another important case is when word appears exactly once but repeated versions do not. For example:

sequence = "ababc"
word = "ba"

Here, "ba" exists, but "baba" does not, so the answer is 1.

We should also consider overlapping patterns. For example:

sequence = "aaaaa"
word = "aa"

The repeated substring "aaaa" appears, meaning k = 2 works, even though occurrences overlap conceptually.

The problem guarantees that both strings contain only lowercase English letters and are non-empty, so we do not need to handle empty strings or invalid input.

Approaches

Brute Force Approach

A straightforward way to solve this problem is to try every possible value of k and check whether word * k exists as a substring of sequence.

We can begin with k = 1 and repeatedly concatenate word to itself. For each repetition, we test whether the resulting string appears inside sequence.

Eventually, one of two things happens:

  1. The repeated string is no longer a substring.
  2. The repeated string becomes longer than sequence, making further checks pointless.

The largest successful k is our answer.

This approach is correct because it explicitly checks every possible candidate in increasing order. Since we stop only when a repetition fails, the final valid count must be the maximum one.

However, repeatedly rebuilding strings and scanning for substrings can become inefficient. Although the constraints are small enough that this solution works comfortably, we can reason about it more carefully and structure the process better.

Optimal Approach

The key observation is that the maximum possible repetition count is naturally bounded.

If word has length m and sequence has length n, then:

maximum possible k = n // m

Anything larger would exceed the total length of sequence, making it impossible to fit.

Instead of blindly increasing k, we can iterate through all feasible repetition counts and check whether the repeated string exists in sequence.

Since substring search in Python and Go is efficient and the constraints are tiny, this becomes a clean and practical solution.

We repeatedly build:

word
word * 2
word * 3
...

and track the largest valid repetition count.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly builds strings and checks substrings incrementally
Optimal O(n²) O(n) Limits checks to feasible repetition counts and stops unnecessary work

Since n ≤ 100, both approaches are easily fast enough. The optimal version is cleaner and better structured.

Algorithm Walkthrough

Optimal Algorithm

  1. Compute the maximum possible repetition count.

Since repeated copies of word must fit inside sequence, the maximum number of repetitions cannot exceed:

len(sequence) // len(word)

This gives us an upper bound and avoids unnecessary checks. 2. Initialize a variable to track the answer.

We maintain max_repeating = 0 so we can update it whenever we find a valid repeated substring. 3. Iterate through all possible repetition counts.

For each value of k from 1 to the maximum possible repetition count, construct:

repeated_word = word * k
  1. Check whether the repeated string is a substring of sequence.

If:

repeated_word in sequence

then k is valid, so update max_repeating. 5. Return the largest valid repetition count.

After testing all feasible values of k, return the stored maximum.

Why it works

The algorithm works because it systematically checks every valid candidate repetition count in increasing order. Since every possible k between 1 and the theoretical maximum is tested, no valid answer can be missed. The algorithm records only successful repetitions, ensuring the final result is the largest valid k.

Python Solution

class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        max_possible = len(sequence) // len(word)
        max_repeating = 0

        for k in range(1, max_possible + 1):
            repeated_word = word * k

            if repeated_word in sequence:
                max_repeating = k

        return max_repeating

The implementation begins by calculating the maximum possible number of repetitions. Since a repeated substring cannot be longer than sequence, we use integer division to establish an upper bound.

We then initialize max_repeating to 0, which correctly handles cases where word never appears in sequence.

The for loop iterates through every feasible repetition count. For each k, we construct the repeated pattern using:

word * k

Python string multiplication makes this concise and efficient.

We then check whether the generated string appears inside sequence using Python's built-in substring operation:

repeated_word in sequence

If the substring exists, we update the answer.

Finally, after checking every candidate repetition count, we return the largest valid value.

Go Solution

func maxRepeating(sequence string, word string) int {
    maxPossible := len(sequence) / len(word)
    maxRepeating := 0

    for k := 1; k <= maxPossible; k++ {
        repeatedWord := ""

        for i := 0; i < k; i++ {
            repeatedWord += word
        }

        if contains(sequence, repeatedWord) {
            maxRepeating = k
        }
    }

    return maxRepeating
}

func contains(sequence string, target string) bool {
    return strings.Contains(sequence, target)
}

The Go implementation follows the same overall logic as the Python version.

Unlike Python, Go does not support string multiplication such as:

word * k

so we construct the repeated string manually using a loop.

Substring checking is handled with:

strings.Contains(sequence, repeatedWord)

This requires importing the strings package.

Go strings are immutable, just like Python strings, but given the tiny input constraints, repeated concatenation is perfectly acceptable here.

A fully LeetCode-submittable version with imports looks like this:

import "strings"

func maxRepeating(sequence string, word string) int {
    maxPossible := len(sequence) / len(word)
    maxRepeating := 0

    for k := 1; k <= maxPossible; k++ {
        repeatedWord := ""

        for i := 0; i < k; i++ {
            repeatedWord += word
        }

        if strings.Contains(sequence, repeatedWord) {
            maxRepeating = k
        }
    }

    return maxRepeating
}

Worked Examples

Example 1

sequence = "ababc"
word = "ab"

Maximum possible repetitions:

5 // 2 = 2
k repeated_word In sequence? max_repeating
1 "ab" Yes 1
2 "abab" Yes 2

Final answer:

2

Example 2

sequence = "ababc"
word = "ba"

Maximum possible repetitions:

5 // 2 = 2
k repeated_word In sequence? max_repeating
1 "ba" Yes 1
2 "baba" No 1

Final answer:

1

Example 3

sequence = "ababc"
word = "ac"

Maximum possible repetitions:

5 // 2 = 2
k repeated_word In sequence? max_repeating
1 "ac" No 0
2 "acac" No 0

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Up to n / m substring checks, each potentially scanning O(n) characters
Space O(n) Temporary repeated strings can grow up to the size of sequence

Let n be the length of sequence and m be the length of word.

The loop runs at most n / m times. During each iteration, we build a repeated string and check whether it exists inside sequence. In the worst case, substring matching can take O(n) time, giving an overall complexity of approximately O(n²).

The space complexity is O(n) because the largest repeated string may become as large as the entire sequence.

Test Cases

solution = Solution()

assert solution.maxRepeating("ababc", "ab") == 2  # basic repeated substring
assert solution.maxRepeating("ababc", "ba") == 1  # single occurrence only
assert solution.maxRepeating("ababc", "ac") == 0  # word not present

assert solution.maxRepeating("aaaaa", "aa") == 2  # overlapping repetitions
assert solution.maxRepeating("abcabcabc", "abc") == 3  # exact multiple
assert solution.maxRepeating("abcabcab", "abc") == 2  # partial final repetition

assert solution.maxRepeating("a", "a") == 1  # minimum input size
assert solution.maxRepeating("b", "a") == 0  # smallest no-match case

assert solution.maxRepeating("zzzzzz", "z") == 6  # single-character repetition
assert solution.maxRepeating("abababab", "ab") == 4  # many repetitions

assert solution.maxRepeating("xyz", "xyzxyz") == 0  # word longer than sequence
assert solution.maxRepeating("aaaaaa", "aaa") == 2  # exact repeated block

Test Summary

Test Why
"ababc", "ab" Validates repeated substring detection
"ababc", "ba" Ensures single occurrence works
"ababc", "ac" Confirms missing substring returns 0
"aaaaa", "aa" Tests overlapping behavior
"abcabcabc", "abc" Verifies exact repeated sequence
"abcabcab", "abc" Checks incomplete trailing repetition
"a", "a" Minimum valid input
"b", "a" Minimum no-match case
"zzzzzz", "z" Single-character repetition
"abababab", "ab" Larger repetition count
"xyz", "xyzxyz" Word longer than sequence
"aaaaaa", "aaa" Exact repeated chunks

Edge Cases

One important edge case occurs when word does not appear in sequence at all. A naive implementation might accidentally return 1 if it assumes at least one repetition exists. Our implementation avoids this issue by initializing max_repeating = 0 and updating it only when a valid substring is found.

Another edge case is when word overlaps with itself. For example:

sequence = "aaaaa"
word = "aa"

Even though the occurrences overlap conceptually, the repeated substring "aaaa" still exists contiguously inside the sequence, meaning k = 2 is valid. Since we check the repeated concatenated string directly, overlapping behavior is naturally handled without special logic.

A third important case occurs when word is longer than sequence. In this situation, no repetition can possibly fit. Because we compute:

len(sequence) // len(word)

the maximum possible repetition count becomes 0, meaning the loop never runs and the function correctly returns 0.

Finally, single-character strings deserve attention because they can produce very large repetition counts relative to input size. For example:

sequence = "zzzzzz"
word = "z"

Our implementation correctly checks every feasible repetition level and returns 6, demonstrating that the logic works even for extreme repetition density.