algoadvance

Leetcode 1668. Maximum Repeating Substring

Problem Statement:

1668. Maximum Repeating Substring

Given a string sequence and a string word, return the maximum number of times word can be repeated in sequence as a substring.

Clarifying Questions:

1. Can the word overlap within the sequence?
   • No, we are looking for non-overlapping instances of word when it is repeated.
2. What is the length range for sequence and word?
   • The length of sequence and word doesn’t exceed (100) characters.
3. Can sequence or word be empty strings?
   • According to the problem constraints, neither sequence nor word would be empty.

Strategy:

1. Concatenate word Multiple Times: Create increasingly longer strings of repeated word (e.g., word, word+word, word+word+word, etc.).

2. Check Substring Existence: For each concatenated string, check if it is a substring of sequence.

3. Optimize Checking: Stop as soon as the concatenated string is no longer found in sequence.

Code:

#include <iostream>
#include <string>

using namespace std;

int maxRepeating(string sequence, string word) {
    int maxRepeat = 0;
    string repeatedWord = word;

    while (sequence.find(repeatedWord) != string::npos) {
        maxRepeat++;
        repeatedWord += word;
    }

    return maxRepeat;
}

int main() {
    string sequence = "ababc";
    string word = "ab";
    cout << "Maximum repeating: " << maxRepeating(sequence, word) << endl;
    return 0;
}

Time Complexity:

• Worst-case scenario: The outer loop runs as long as the length of repeatedWord is within the length of sequence. Suppose n is the length of sequence and m is the length of word.
• Each concatenation operation takes (O(k \cdot m)) time for the kth concatenated string and checking for a substring takes (O(n)) in the worst case. However, the overall complexity is dominated by the increasing size of repeatedWord.
• The overall time complexity approximates to (O((n/m) \cdot n)), which simplifies to (O(n^2 / m)).

Explanation:

1. Concatenate: We keep concatenating word to a temporary repeatedWord string.
2. Substring Check: We use find to check if repeatedWord is in sequence.
3. Increment: If found, we increase the count and continue; otherwise, stop and return the count.

This ensures that we correctly identify the maximum number of times word can be repeated consecutively within sequence.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?