1668. Maximum Repeating Substring
Problem Description
The problem involves finding the highest number of times (k
) a word can repeat itself as a contiguous subsequence within a larger string. For example, if the sequence
is "ababc" and the word
is "ab", then the word "ab" repeats once as a substring. However, it does not repeat twice in a row, so it cannot be considered 2-repeating. The task is to find the maximum k
-repeating value, which means we want to find the highest number of consecutive repetitions of word
within sequence
.
If word
does not appear in sequence
even once, then the maximum k
-repeating value is 0. The goal is to return this maximum k
value.
Intuition
The intuition behind the solution is a straightforward search approach. We know that the maximum k
value cannot be more than the number of times word
can fit into sequence
, which is len(sequence) // len(word)
. We start checking from the maximum possible repetition (k value) and work backwards. In each iteration, we construct a string by repeating word
k
times and check if that construction is a substring of sequence
. If it is, that means word
is k
-repeating in sequence
, and we have found our maximum k
-repeating value.
The reason we start from the maximum and go backwards is efficiency; it saves us from checking all values of k
from 1
upwards. As soon as we find the first k
that satisfies the condition, we know that it's the maximum because all higher values would not fit the definition of a substring due to exceeding the length of sequence
.
Solution Approach
The given solution method maxRepeating
defines a simple approach, utilizing a control structure to find the maximum k
-repeating value. It uses a for
loop and string multiplication operations to achieve this.
Here's a step-by-step overview of the algorithm:
-
First, we need to establish the upper bound of our search for
k
. The most number of timesword
can fit intosequence
is found through integer division (//
). This is calculated bylen(sequence) // len(word)
. It gives us the maximum number of timesword
can be repeated before it would exceed the length ofsequence
. -
We then use a
for
loop to iterate from this maximum possible value ofk
down to0
. The reason for iterating backwards is to find the maximumk
-repeating value first. If we were to iterate forwards, we would need to check every possible value ofk
upto the maximum, which is less efficient. -
In each iteration of the loop, we create a new string by multiplying
word
byk
. The multiplication operator*
used on strings in Python creates a new string by repeating the operand stringk
times. -
We then check if this newly created string is a substring of
sequence
by using thein
operator in Python, which returnsTrue
if the first operand is found within the second operand string. -
If the condition
word * k in sequence
is true, the loop breaks and returns the current value ofk
, which is the maximumk
-repeating value. -
If the loop completes without finding any
k
value for whichword * k
is a substring ofsequence
, the function implicitly returnsNone
, which is not relevant to our problem statement since we expect an integer. -
The choice of using this specific pattern is due to its simplicity and effectiveness for the given problem. No additional data structures are needed, and the control flow along with built-in string operations is sufficient to arrive at the correct result.
With this approach, we minimize the number of checks we need to perform and ensure that we can return the highest k
as soon as it is found.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through an example to illustrate the solution approach. For this example, let's take the sequence
as "aabbabbabbaabbaabb" and the word
as "abb".
-
Establish the upper bound: According to step 1, we find the maximum number of times
word
can fit intosequence
. We getlen(sequence) // len(word)
which is18 // 3 = 6
. Thus, the word "abb" can be repeated at most 6 times in a row without exceeding the length of the sequence. -
Iterate from the maximum possible value of
k
down to 0: We start a for loop from6
down to1
. -
String multiplication and substring check: In the first iteration,
k
is6
, so we multiply "abb" by6
. We check if "abbabbabbabbabbabb" (word * k
) is a substring of the sequence "aabbabbabbaabbaabb". It isn't, so we continue the loop withk
decremented by1
. -
Repeat step 3 with
k = 5, 4, 3, ...
, constructing the string "abb" *k
each time and checking if it's a substring of "aabbabbabbaabbaabb". -
When
k = 3
, we build "abbabbabb" (which is "abb" repeated 3 times) and check if it's a substring of the sequence. We find that "aabbabbabbaabbaabb" does contain "abbabbabb". Thus,word
doesk
-repeat fork = 3
. -
The function then breaks from the loop and returns
3
, as this is the highestk
value for whichword * k
is a subsequence of thesequence
.
Using this approach, we efficiently found the highest number of contiguous subsequences of "abb" within the larger string "aabbabbabbaabbaabb" by starting from the largest possible repetition (k) and reducing it until we found a match.
Solution Implementation
1class Solution:
2 def max_repeating(self, sequence: str, word: str) -> int:
3 """
4 Find the maximum number of times 'word' can be consecutively repeated
5 in 'sequence' as a substring.
6
7 :param sequence: The string in which to search for repeating 'word'.
8 :param word: The word to look for in 'sequence'.
9 :return: The maximum number of times 'word' can be repeated.
10 """
11
12 # Calculate the maximum possible repetitions of 'word' within 'sequence'
13 max_possible_repeats = len(sequence) // len(word)
14
15 # Iterate over the possible repetitions, starting from the most and descending
16 for k in range(max_possible_repeats, -1, -1):
17 # If the repeat sequence of 'word' is within 'sequence', return that repeat count
18 if word * k in sequence:
19 return k
20
21 # If no repetition of 'word' is found, we return 0
22 return 0 # Technically this line is not necessary due to the loop's range
23
1class Solution {
2 // Defines a method to find the maximum number of times 'word' repeats in 'sequence'
3 public int maxRepeating(String sequence, String word) {
4 // Start from the maximum possible repetitions and decrement
5 for (int k = sequence.length() / word.length(); k > 0; --k) {
6 String repeatedWord = word.repeat(k); // Construct the word repeated 'k' times
7 if (sequence.contains(repeatedWord)) { // Check if 'sequence' contains the repeated 'word'
8 return k; // If found, return the current repetition count 'k'
9 }
10 }
11 return 0; // If no repetition is found, return 0
12 }
13}
14
1#include <string>
2using namespace std;
3
4class Solution {
5public:
6 // This function finds the maximum number of times 'word' can be repeated
7 // consecutively in the string 'sequence'.
8 int maxRepeating(string sequence, string word) {
9 int maxCount = 0; // Stores the maximum count of repeating 'word'
10 string repeatedWord = word; // Starts with one 'word' and we'll append more
11 int possibleRepeats = sequence.size() / word.size(); // Calculates the maximum possible times 'word' could repeat
12
13 // Loop repeats until 'word' can no longer fit into 'sequence'
14 for (int k = 1; k <= possibleRepeats; ++k) {
15 // Check if the current 'repeatedWord' is a substring of 'sequence'
16 if (sequence.find(repeatedWord) != string::npos) {
17 maxCount = k; // Update the maxCount to the current repetition number
18 } else {
19 // If the 'repeatedWord' is not in 'sequence', break out of the loop
20 break;
21 }
22
23 // Append 'word' to 'repeatedWord' for the next iteration to check for the next number of repeats
24 repeatedWord += word;
25 }
26
27 // Return the maxCount, which is the maximum number of times 'word' repeats consecutively in 'sequence'
28 return maxCount;
29 }
30};
31
1/**
2 * Find the maximum number of times the word can be repeated consecutively in the sequence.
3 * @param {string} sequence - The string to search within.
4 * @param {string} word - The word to look for in the sequence.
5 * @returns {number} The maximum number of times the word is repeated.
6 */
7function maxRepeating(sequence: string, word: string): number {
8 // Determine the lengths of the sequence and the word
9 let sequenceLength: number = sequence.length;
10 let wordLength: number = word.length;
11
12 // Start from the maximum possible repetition (sequence length divided by word length)
13 // and go down to find the maximum repeating consecutive occurrences
14 for (let repeatCount: number = Math.floor(sequenceLength / wordLength); repeatCount > 0; repeatCount--) {
15
16 // Generate the word repeated 'repeatCount' times
17 let repeatedWord: string = word.repeat(repeatCount);
18
19 // Check if the sequence includes the repeated word
20 if (sequence.includes(repeatedWord)) {
21 // If the sequence contains the word repeated 'repeatCount' times, return 'repeatCount' as the result
22 return repeatCount;
23 }
24 }
25
26 // If no repetition is found, return 0
27 return 0;
28}
29
Time and Space Complexity
Time Complexity:
The given code finds the maximum number of times the word word
can be repeated in the sequence
string. It checks for every k
from len(sequence) // len(word)
down to 0
to see if word * k
is a substring of the sequence
.
The time complexity of checking if a string is a substring of another string is O(n), where n is the length of the string. Here, it is checking a substring of maximum length len(word) * k
in a string of length len(sequence)
. This needs to be done for each k from len(sequence) // len(word)
to 0
.
Therefore, the time complexity can be approximated as O((n/m) * (n + n - m + n - 2m + ... + m)), where n is len(sequence)
and m is len(word)
. This simplifies to O((n^2/m) * (n/m)) = O(n^3/m^2).
Space Complexity:
The space complexity of the code is O(n), with n being the maximum length of word * k
which can be generated for the comparison with sequence
. Essentially, the space required is for the substring that is created during word * k
. The memory used grows linearly with the size of this generated string, which is at most the length of sequence
itself.
Learn more about how to find time and space complexity quickly using problem constraints.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
14
1public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
1function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!