problemeasyalgorithmsleetcode-1668leetcode 1668leetcode1668

Maximum Repeating Substring

EasyUpdated: Jan 1, 2025
Practice on:
LeetCode

Problem

For a string sequence, a string word is k-repeating if word concatenated k times is a substring of sequence. The word's maximumk-repeating value is the highest value k where word is k-repeating in sequence. If word is not a substring of sequence, word's maximum k-repeating value is 0.

Given strings sequence and word, return themaximumk-repeating value of word in sequence.

Examples

Example 1

Input: sequence = "ababc", word = "ab"
Output: 2
Explanation: "abab" is a substring in "_abab_ c".

Example 2

Input: sequence = "ababc", word = "ba"
Output: 1
Explanation: "ba" is a substring in "a _ba_ bc". "baba" is not a substring in "ababc".

Example 3

Input: sequence = "ababc", word = "ac"
Output: 0
Explanation: "ac" is not a substring in "ababc".

Method 1 – Brute Force with String Multiplication

Intuition

The key idea is to check how many times we can repeat the word and still find it as a substring in the sequence. We keep increasing the count until the repeated word is no longer a substring.

Approach

  1. Initialize a counter k to 0.
  2. While the sequence contains the word repeated k+1 times, increment k.
  3. Return k as the answer.

This approach is simple and leverages built-in string operations.

Code

C++
class Solution {
public:
    int maxRepeating(string sequence, string word) {
        int k = 0;
        string t = word;
        while (sequence.find(t) != string::npos) {
            k++;
            t += word;
        }
        return k;
    }
};
Go
func maxRepeating(sequence string, word string) int {
    k := 0
    t := word
    for strings.Contains(sequence, t) {
        k++
        t += word
    }
    return k
}
Java
class Solution {
    public int maxRepeating(String sequence, String word) {
        int k = 0;
        String t = word;
        while (sequence.contains(t)) {
            k++;
            t += word;
        }
        return k;
    }
}
Kotlin
class Solution {
    fun maxRepeating(sequence: String, word: String): Int {
        var k = 0
        var t = word
        while (sequence.contains(t)) {
            k++
            t += word
        }
        return k
    }
}
Python
class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        k = 0
        t = word
        while t in sequence:
            k += 1
            t += word
        return k
Rust
impl Solution {
    pub fn max_repeating(sequence: String, word: String) -> i32 {
        let mut k = 0;
        let mut t = word.clone();
        while sequence.contains(&t) {
            k += 1;
            t += &word;
        }
        k
    }
}
TypeScript
class Solution {
    maxRepeating(sequence: string, word: string): number {
        let k = 0;
        let t = word;
        while (sequence.includes(t)) {
            k++;
            t += word;
        }
        return k;
    }
}

Complexity

  • ⏰ Time complexity: O(n * m * k), where n is the length of sequence, m is the length of word, and k is the maximum number of repetitions. Each check for substring can take up to O(n), and we do this up to k times, where k can be up to n/m.
  • 🧺 Space complexity: O(m * k), for the temporary string t which grows by m each time up to k times.

Comments