1. Maximum Repeating Substring (LeetCode)
Model answer
The task
Given a string sequence and a nonempty string word, find the largest number of consecutive copies of word that appear as a substring of sequence.
Key idea
Use dynamic programming from right to left. If word begins at position i, the count there is one plus the count beginning immediately after it. This enforces consecutive copies; separate or overlapping matches do not add to the count.
Approach
- Let
dp[i]be the maximum number of consecutive copies starting at indexi. - Visit positions from right to left so the value at
i + len(word)is already known. - When the slice at
imatchesword, setdp[i] = 1 + dp[i + len(word)]. - Track and return the largest value.
class Solution:
def maxRepeating(self, sequence: str, word: str) -> int:
n = len(sequence)
m = len(word)
if m == 0:
return 0
# dp[i] counts consecutive copies of word starting at i.
dp = [0] * (n + 1)
best = 0
for i in range(n - m, -1, -1):
if sequence[i:i + m] == word:
dp[i] = 1 + dp[i + m]
best = max(best, dp[i])
return best
Complexity:
- Time: O(n · m), where each of up to
npositions may compare a slice of lengthm. - Space: O(n), for the dynamic-programming array.
Common follow-ups
- How can matching be made more efficient for long strings? Use a string-matching algorithm such as KMP to find occurrences, then combine occurrences separated by exactly
len(word). - Do overlapping occurrences count? Only if they form consecutive, non-overlapping copies of
word. - What if
wordis empty? This implementation returns0; the usual problem definition assumes a nonempty word.