Maximum Repeating Substring

Difficulty: Easy | Acceptance: 41.60% | Paid: No Topics: String, Dynamic Programming, String Matching

For a string sequence, a string word is k-repeating if word concatenated k times is a substring of sequence. The word’s maximum k-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 the maximum k-repeating value of word in sequence.

Examples

Example 1

Input:

sequence = "ababc", word = "ab"

Output:

2

Explanation: “abab” is a substring in “ababc”.

Example 2

Input:

sequence = "ababc", word = "ba"

Output:

1

Explanation: “ba” is a substring in “ababc”. “baba” is not a substring in “ababc”.

Example 3

Input:

sequence = "ababc", word = "ac"

Output:

0

Explanation: “ac” is not a substring in “ababc”.

Constraints

1 <= sequence.length <= 100
1 <= word.length <= 100
sequence and word consist of lowercase English letters.

• Brute Force Simulation
• Dynamic Programming
• KMP Algorithm

Examples

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

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

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

Constraints

1 <= sequence.length <= 100
1 <= word.length <= 100
sequence and word consist of lowercase English letters.

Brute Force Simulation

Intuition Since the constraints are small (length ≤ 100), we can simply simulate the process by repeatedly concatenating word and checking if the result exists in sequence.

Steps

• Initialize k = 0.
• Loop while word repeated k + 1 times is a substring of sequence.
• Increment k in each iteration.
• Return k.

class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        k = 0
        while word * (k + 1) in sequence:
            k += 1
        return k

Complexity

• Time: O(n²) in the worst case, where n is the length of sequence. The in / contains check can be O(n*m) or O(n) depending on implementation, and we do it up to n/m times.
• Space: O(n) to store the repeated string.
• Notes: Simple to implement and efficient enough for the given constraints.

Dynamic Programming

Intuition We can define dp[i] as the maximum k-repeating value ending at index i in sequence. If the substring ending at i matches word, we can extend the count from the position i - len(word).

Steps

• Initialize a dp array of size n (length of sequence) with zeros.
• Iterate through sequence from index len(word) - 1 to n - 1.
• Check if the substring sequence[i - len(word) + 1 : i + 1] equals word.
• If it matches, dp[i] = dp[i - len(word)] + 1.
• Keep track of the maximum value in the dp array.

class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        n = len(sequence)
        m = len(word)
        dp = [0] * n
        ans = 0
        for i in range(m - 1, n):
            if sequence[i - m + 1 : i + 1] == word:
                dp[i] = (dp[i - m] if i >= m else 0) + 1
                ans = max(ans, dp[i])
        return ans

Complexity

• Time: O(n * m) where n is the length of sequence and m is the length of word. Substring comparison takes O(m).
• Space: O(n) for the DP array.
• Notes: More efficient than brute force for larger inputs and avoids repeated string concatenation.

KMP Algorithm

Intuition We can use the Knuth-Morris-Pratt algorithm to find all occurrences of word in sequence. Once we have the starting indices of all matches, we can iterate through them to find the longest chain of consecutive matches separated by exactly word.length.

Steps

• Compute the LPS (Longest Prefix Suffix) array for word.
• Use the KMP search algorithm to find all start indices of word in sequence.
• Iterate through the sorted list of start indices.
• If the current index is exactly word.length greater than the previous index, increment the current chain count; otherwise, reset the chain count to 1.
• Track the maximum chain count found.

class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        def kmp_search(s, p):
            lps = [0] * len(p)
            # Build LPS
            length = 0
            i = 1
            while i < len(p):
                if p[i] == p[length]:
                    length += 1
                    lps[i] = length
                    i += 1
                else:
                    if length != 0:
                        length = lps[length - 1]
                    else:
                        lps[i] = 0
                        i += 1
            
            # Search
            i = 0 # index for s
            j = 0 # index for p
            indices = []
            while i < len(s):
                if s[i] == p[j]:
                    i += 1
                    j += 1
                if j == len(p):
                    indices.append(i - j)
                    j = lps[j - 1]
                elif i < len(s) and s[i] != p[j]:
                    if j != 0:
                        j = lps[j - 1]
                    else:
                        i += 1
            return indices

        matches = kmp_search(sequence, word)
        if not matches:
            return 0
        
        max_k = 1
        curr_k = 1
        m = len(word)
        for i in range(1, len(matches)):
            if matches[i] == matches[i - 1] + m:
                curr_k += 1
                max_k = max(max_k, curr_k)
            else:
                curr_k = 1
        return max_k

Complexity

• Time: O(n + m) for the KMP search and LPS construction, where n is the length of sequence and m is the length of word. Sorting indices is O(k log k) where k is the number of matches, but since we find them in order, we can just iterate, making it O(n + m).
• Space: O(m) for the LPS array and O(k) for storing match indices.
• Notes: Optimal time complexity for string matching, though more complex to implement than necessary for the given constraints.