This is an easy level coding interview problem from leetcode. The problem asks you to find the maximum number of repeating string which is given. Please refer to the problem description for more detail. For the solution, you need to iterate the sequence. At each index, you check if the substring matches the word. If it matches, then continue to the next index to find the end of the repeated word. If it doesn’t match, then just move on to the next index.
I provided solutions in C++ and Python3. You can try iterative solution but I provided recursive solutions here. For recursive solutions, it is following the same principles. But note that I keep track of the start index of the comparison because that will be used when the substring doesn’t match.
void maxRepeating(const string &seq, int currIdx, int matchIdx, const string &word, int numRepeat, int &maxRepeat)
{
// this is base case. make sure you get the max repeat.
if (seq.size() - matchIdx < word.size())
{
maxRepeat = max(maxRepeat, numRepeat);
}
// word doesn't match. get the max repeat and then continue comparing the string from the currIdx which is the start of the matching
else if (seq.substr(matchIdx, word.size()) != word)
{
maxRepeat = max(maxRepeat, numRepeat);
maxRepeating(seq, currIdx + 1, currIdx + 1, word, 0, maxRepeat);
}
// word matches. keep checking. make sure currIdx is passed to note the start of the pattern
else
{
maxRepeating(seq, currIdx, matchIdx + word.size(), word, numRepeat + 1, maxRepeat);
}
}
int maxRepeating(string sequence, string word) {
int maxRepeat = 0;
maxRepeating(sequence, 0, 0, word, 0, maxRepeat);
return maxRepeat;
}class Solution:
result = 0
def max_repeating(self, sequence, curr_idx, match_idx, word, num_repeat):
compare = sequence[match_idx : match_idx + len(word)]
if len(compare) < len(word):
self.result = max(self.result, num_repeat)
return
elif compare != word:
self.result = max(self.result, num_repeat)
self.max_repeating(sequence, curr_idx + 1, curr_idx + 1, word, 0)
return
self.max_repeating(sequence, curr_idx, match_idx + len(word), word, num_repeat + 1)
def maxRepeating(self, sequence: str, word: str) -> int:
self.max_repeating(sequence, 0, 0, word, 0)
return self.result