1668. Maximum Repeating Substring

EasyStringString Matching

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which type of traversal does breadth first search do?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

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 times word can fit into sequence is found through integer division (//). This is calculated by len(sequence) // len(word). It gives us the maximum number of times word can be repeated before it would exceed the length of sequence.
We then use a for loop to iterate from this maximum possible value of k down to 0. The reason for iterating backwards is to find the maximum k-repeating value first. If we were to iterate forwards, we would need to check every possible value of k upto the maximum, which is less efficient.
In each iteration of the loop, we create a new string by multiplying word by k. The multiplication operator * used on strings in Python creates a new string by repeating the operand string k times.
We then check if this newly created string is a substring of sequence by using the in operator in Python, which returns True 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 of k, which is the maximum k-repeating value.
If the loop completes without finding any k value for which word * k is a substring of sequence, the function implicitly returns None, 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Determine state to pass down to recursive function callDetermine return valueDetermine how many recursive calls will be madeTracing the recursive calls

Example 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 into sequence. We get len(sequence) // len(word) which is 18 // 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 from 6 down to 1.
String multiplication and substring check: In the first iteration, k is 6, so we multiply "abb" by 6. We check if "abbabbabbabbabbabb" (word * k) is a substring of the sequence "aabbabbabbaabbaabb". It isn't, so we continue the loop with k decremented by 1.
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 does k-repeat for k = 3.
The function then breaks from the loop and returns 3, as this is the highest k value for which word * k is a subsequence of the sequence.

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

Not Sure What to Study? Take the 2-min Quiz：

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's fasterIt has better space complexityOrder of computer subproblems does not matterIt has better time complexity

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1668. Maximum Repeating Substring

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings