For a string sequence, a string word is k-repeating if word concatenated k times is a…
- 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
- Assistant
The most efficient way to solve this problem given the constraints is by iterating through each position in the
sequenceand attempting to match thewordrepeatedly 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_kThis approach avoids unnecessary string concatenations and checks for the repeated occurrence of
wordstarting from each index in thesequence. It runs efficiently within the given constraints.