#1668

Easy

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Maximum Repeating Substring

Find the maximum number of times a given word repeats consecutively in a string using state transition dynamic programming.

string dynamic programming string matching

Problem Statement

Given two strings, sequence and word, determine the maximum number of times word repeats consecutively as a substring in sequence. A word is considered k-repeating if the word concatenated k times appears as a substring in sequence. If the word does not appear in sequence at all, the result is 0.

For example, with sequence = "ababc" and word = "ab", the word "ab" repeats twice as a substring in the sequence, making the maximum k-repeating value 2. For words that do not appear in the sequence, the k-repeating value is 0.

Examples

Example 1

Input: sequence = "ababc", word = "ab"

Output: 2

"abab" is a substring in "ababc".

Example 2

Input: sequence = "ababc", word = "ba"

Output: 1

"ba" is a substring in "ababc". "baba" is not a substring in "ababc".

Example 3

Input: sequence = "ababc", word = "ac"

Output: 0

"ac" is not a substring in "ababc".

Constraints

1 <= sequence.length <= 100
1 <= word.length <= 100
sequence and word contains only lowercase English letters.

Solution Approach

Brute Force Search

One approach is to check all possible substrings of sequence that start with word, increasing the count of consecutive repetitions until it no longer forms a valid substring. This approach is feasible for small inputs but may not scale well for larger strings.

State Transition Dynamic Programming

Dynamic programming can be used to optimize the search for k-repeating words. By tracking the states of repetition and transitioning based on substring matches, we can efficiently calculate the maximum value of k, avoiding redundant calculations and reducing time complexity.

Optimized Sliding Window

An alternative solution involves using a sliding window over the sequence. This method checks for repetitions of word while sliding across the sequence. It’s efficient when combined with early exits for unmatched conditions, further improving performance over brute force.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time and space complexities depend on the chosen approach. The brute force method has a time complexity of O(n^2), where n is the length of the sequence, while dynamic programming can reduce this to O(n). Sliding window optimization may also achieve O(n) time complexity, with space complexity varying based on the implementation.

What Interviewers Usually Probe

Understanding dynamic programming principles, especially state transitions.
Ability to recognize the need for optimization when brute force becomes inefficient.
Knowledge of string matching techniques like sliding windows and substring searches.

Common Pitfalls or Variants

Common pitfalls

Overlooking edge cases where the word doesn't appear in the sequence at all.
Not optimizing the solution when brute force becomes too slow for larger inputs.
Misunderstanding how to track repeated substrings efficiently using dynamic programming.

Follow-up variants

Consider the case where the sequence contains multiple different words and you need to find the maximum k-repeating value for each.
Explore optimizing the space complexity of the dynamic programming approach for even larger inputs.
Extend the problem to allow the word to repeat non-consecutively and calculate the number of total occurrences.

FAQ

How can dynamic programming help solve the Maximum Repeating Substring problem?

Dynamic programming helps track the state of consecutive word repetitions in the sequence, ensuring efficient calculation of the maximum k-repeating value.

What is the time complexity of the brute force approach for this problem?

The brute force approach has a time complexity of O(n^2), where n is the length of the sequence, due to checking all possible substrings.

What is the best approach for large inputs in the Maximum Repeating Substring problem?

Dynamic programming or optimized sliding window techniques are better suited for large inputs, offering O(n) time complexity.

Can the solution be optimized further using string matching algorithms?

Yes, advanced string matching algorithms such as KMP or Rabin-Karp could be applied to further optimize the substring search process.

What are the edge cases to consider in this problem?

Edge cases include when the word does not appear in the sequence at all or when the sequence is too short to contain any repetition of the word.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

class Solution:
    def maxRepeating(self, sequence: str, word: str) -> int:
        for k in range(len(sequence) // len(word), -1, -1):
            if word * k in sequence:
                return k

Continue Practicing

#1397 find all good strings #2430 maximum deletions on a string #1653 minimum deletions to make string balanced