Leetcode 1668: Maximum Repeating Substring
You are given two strings:
sequence and word. A string word is considered ‘k-repeating’ in sequence if word concatenated k times forms a substring of sequence. The task is to return the maximum value of k such that word repeated k times appears as a substring in sequence. If no such substring exists, return 0.Problem
Approach
Steps
Complexity
Input: You are given two strings, `sequence` and `word`.
Example: sequence = 'xyzxyzxyz', word = 'xyz'
Constraints:
• 1 <= sequence.length <= 100
• 1 <= word.length <= 100
• Both `sequence` and `word` contain only lowercase English letters.
Output: Return the maximum value of `k` such that `word` repeated `k` times forms a substring of `sequence`.
Example: 3
Constraints:
• If `word` is not a substring of `sequence`, return 0.
Goal: To find the highest value of `k` where `word` repeated `k` times is a substring of `sequence`.
Steps:
• Start with the word and initialize the count of repetitions as 0.
• Keep concatenating `word` and check if the concatenated string exists in `sequence`.
• Stop when the concatenated string is no longer a substring, and return the count of repetitions.
Goal: The constraints ensure that the input sizes are manageable for direct string search operations.
Steps:
• 1 <= sequence.length <= 100
• 1 <= word.length <= 100
Assumptions:
• Both `sequence` and `word` are non-empty strings.
• Input: sequence = 'xyzxyzxyz', word = 'xyz'
• Explanation: The word 'xyz' can be repeated 3 times to form the substring 'xyzxyzxyz' in 'xyzxyzxyz'.
• Input: sequence = 'abcdefg', word = 'xyz'
• Explanation: Since 'xyz' does not exist in 'abcdefg', the maximum k-repeating value is 0.
Approach: To solve this problem, we will simulate the process of concatenating `word` multiple times and check if the resulting string is a substring of `sequence`.
Observations:
• We need to check for increasing repetitions of `word` in the `sequence`.
• Start by checking if the word itself exists in the sequence. Then, iteratively check for more repetitions of the word.
Steps:
• Initialize a counter `k` to 0.
• Concatenate `word` to a temporary string and check if it is a substring of `sequence`.
• Increment `k` each time a valid repetition is found, and stop when the concatenated string is no longer a substring of `sequence`.
Empty Inputs:
• Both `sequence` and `word` will have at least one character, so empty inputs are not a concern.
Large Inputs:
• Ensure that the solution works efficiently for the maximum input sizes, up to 100 characters.
Special Values:
• If `word` does not appear in `sequence`, the result should be 0.
Constraints:
• The solution must handle cases where `word` appears multiple times or not at all.
int maxRepeating(string sequence, string word) {
int count=0;
string temp=word;
while(sequence.find(temp)!=string::npos)
{
count++;
temp+=word;
}
return count;
}
1 : Function Definition
int maxRepeating(string sequence, string word) {
Defines the function `maxRepeating` which takes a string `sequence` and a string `word`, and returns the maximum number of times `word` can repeat in `sequence`.
2 : Variable Initialization
int count=0;
Initializes the variable `count` to keep track of the number of times `word` repeats in `sequence`.
3 : Variable Initialization
string temp=word;
Initializes `temp` with the value of `word`. This string will be used to check for repeated concatenations of `word` in `sequence`.
4 : While Loop
while(sequence.find(temp)!=string::npos)
Begins a loop that continues as long as `temp` is found as a substring in `sequence`.
5 : Counter Increment
count++;
Increments the `count` variable each time `temp` is found in `sequence`.
6 : String Concatenation
temp+=word;
Concatenates `word` to `temp` to check for the next repeated occurrence in `sequence`.
7 : Return Result
return count;
Returns the total count of repeated occurrences of `word` in `sequence`.
Best Case: O(n)
Average Case: O(n * m)
Worst Case: O(n * m)
Description: The time complexity depends on how many times the word can be concatenated and checked as a substring, where `n` is the length of the sequence and `m` is the length of the word.
Best Case: O(1)
Worst Case: O(n)
Description: The space complexity is mainly determined by the storage required to hold the concatenated word and the sequence.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus