Maximum Repeating Substring - Practice Coding Problems

Maximum Repeating Substring - Problem

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.

Input & Output

Example 1 — Basic Repeating Pattern

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

› Output: 2

💡 Note: "ab" appears once, "abab" (ab repeated 2 times) appears as substring in "ababc", but "ababab" (3 times) does not. Maximum k-repeating value is 2.

Example 2 — No Repetition

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

› Output: 1

💡 Note: "ba" appears once in "ababc", but "baba" (repeated 2 times) does not appear. Maximum k-repeating value is 1.

Example 3 — Word Not Found

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

› Output: 0

💡 Note: "ac" does not appear as substring in "ababc". Maximum k-repeating value is 0.

Constraints

1 ≤ sequence.length ≤ 100
1 ≤ word.length ≤ 100
sequence and word consists of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

Given sequence and word to repeat

Process

Find longest consecutive repetition

Output

Return maximum k value

Key Takeaway

🎯 Key Insight: Keep building longer patterns until they no longer exist as substrings

Asked in

G Google 15 M Microsoft 12

The key insight is to incrementally build repeated patterns and check if they exist as substrings. Start with the word itself and keep concatenating until no match is found. Best approach is the optimized incremental building with Time: O(n × k), Space: O(m × k).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Check All Positions	O(n × m × k)	O(m × k)	Check every starting position for each possible repeat count
Optimized Single Pass	O(n × k)	O(m × k)	Build repeated patterns incrementally without recreating strings

Brute Force Check All Positions — Algorithm Steps

Step 1: Start with k=1 and keep incrementing
Step 2: For each k, create word repeated k times
Step 3: Check if this repeated string is substring of sequence
Step 4: Return the maximum k where match was found

Visualization

Tap to expand

Step-by-Step Walkthrough

Try k=1

Check if 'word' exists in sequence

Try k=2

Check if 'wordword' exists in sequence

Continue

Keep trying until no match found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* sequence, char* word) {
    if (strstr(sequence, word) == NULL) {
        return 0;
    }
    
    int maxK = 0;
    int k = 1;
    int wordLen = strlen(word);
    int seqLen = strlen(sequence);
    
    while (true) {
        char* repeatedWord = malloc((k * wordLen + 1) * sizeof(char));
        repeatedWord[0] = '\0';
        
        for (int i = 0; i < k; i++) {
            strcat(repeatedWord, word);
        }
        
        if (strstr(sequence, repeatedWord) != NULL) {
            maxK = k;
            k++;
        } else {
            free(repeatedWord);
            break;
        }
        
        free(repeatedWord);
    }
    
    return maxK;
}

int main() {
    char sequence[1001], word[1001];
    
    fgets(sequence, sizeof(sequence), stdin);
    sequence[strcspn(sequence, "\n")] = 0;
    
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    int result = solution(sequence, word);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m × k)

For each k value, we create string of length k×m and search in string of length n

✓ Linear Growth

Space Complexity

O(m × k)

Store the repeated word string of maximum length m×k

✓ Linear Space

28.4K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Check All Positions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler