algoadvance

Leetcode 1668. Maximum Repeating Substring

Problem Statement

We are given a string sequence and a string word. We need to determine the maximum integer k such that word repeated k times is a substring of sequence.

Clarifying Questions

  1. What is the maximum length of sequence and word? Typically, constraints will mention these values. Let’s assume sequence can be very large, up to 1000 characters, while word can be up to 100 characters.

  2. Can sequence or word contain special characters or whitespace? Assume both can consist of any printable characters, including lowercase and uppercase letters, digits, punctuation, and whitespace.

  3. Is k guaranteed to be at least 1? Yes, the problem implies finding the maximum repeating k, where k is at least 1.

Strategy

To solve this problem, we need to form the repeated versions of word and check whether it is a substring of sequence.

  1. Initialize k to 0 - a variable to keep track of the maximum repeats.
  2. Construct repeated words - Create a string by repeating word k times.
  3. Check for substrings - Continue checking from k=1 to the point where the repeated string cannot be found in sequence.

Steps:

  1. Start with k=1 and repeatedly append word to itself.
  2. Check if the resulting string is a substring of sequence.
  3. If it is, increment k and repeat.
  4. Stop when the repeated word is no longer found in the sequence.
  5. The last valid k is the answer.

Code

Here’s the implementation in Java:

public class MaximumRepeatingSubstring {
    public int maxRepeating(String sequence, String word) {
        int k = 0;
        String repeatedWord = word;
        
        // Try increasing k by checking repeating word["", "word", "wordword", ...] in sequence
        while (sequence.contains(repeatedWord)) {
            k++;
            repeatedWord += word;
        }
        
        return k;
    }

    public static void main(String[] args) {
        MaximumRepeatingSubstring mrs = new MaximumRepeatingSubstring();
        // Example tests
        System.out.println(mrs.maxRepeating("ababc", "ab")); // Output: 2
        System.out.println(mrs.maxRepeating("ababc", "ba")); // Output: 1
        System.out.println(mrs.maxRepeating("ababc", "ac")); // Output: 0
    }
}

Time Complexity

Since these operations are performed up to k times:

  1. String concatenation for k times - O(k * m)
  2. Substring checking performed k times for increasing lengths - O(k * n)

Therefore, the overall time complexity is O(k * (m + n)). In the worst case, k could be approximately n / m.

This ensures an efficient and clear solution for the problem.

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