Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

For a string sequence, a string word is k-repeating if word concatenated k times is a…

  1. User

    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.

    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 contains only lowercase English letters. I need fastest possible python solution

  2. Assistant

    The most efficient way to solve this problem given the constraints is by iterating through each position in the sequence and attempting to match the word repeatedly from that position. Here's how you can do it:

    def maxRepeating(sequence: str, word: str) -> int:
        max_k = 0
        len_seq = len(sequence)
        len_word = len(word)
    
        for i in range(len_seq):
            current_k = 0
            while True:
                start = i + current_k * len_word
                end = start + len_word
                if end > len_seq:
                    break
                if sequence[start:end] == word:
                    current_k += 1
                    max_k = max(max_k, current_k)
                else:
                    break
    
        return max_k
    

    This approach avoids unnecessary string concatenations and checks for the repeated occurrence of word starting from each index in the sequence. It runs efficiently within the given constraints.