Maximum Repeating Substring

Easy
519.

Maximum Repeating Substring

Maximum Repeating Substring is an easy coding problem on strings, asked in Amazon and Adobe interviews.

For a string word and an integer k, word has k-repeating value in sequence if word concatenated k times is a substring of sequence.

Return the maximum such k, or 0 if word is not a substring of sequence at all.

Example 1

Input
sequence = "ababc", word = "ab"
Output
2
Explanation
"abab" occurs; "ababab" does not.

Example 2

Input
sequence = "ababc", word = "ba"
Output
1

Example 3

Input
sequence = "ababc", word = "ac"
Output
0

Constraints

  • 1 <= sequence.length <= 100
  • 1 <= word.length <= 100
  • Both strings consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} sequence
 * @param {string} word
 * @return {number}
 */
var maxRepeating = function(sequence, word) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Repeating Substring — Solution in Python, Java & C++

Maximum Repeating Substring solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on strings.

Maximum Repeating Substring is an easy coding problem on strings, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Strings
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

For a string word and an integer k, word has k-repeating value in sequence if word concatenated k times is a substring of sequence.

Return the maximum such k, or 0 if word is not a substring of sequence at all.

Example 1

Input: sequence = "ababc", word = "ab"
Output: 2
Explanation: "abab" occurs; "ababab" does not.

Example 2

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

Example 3

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

Constraints

  • 1 <= sequence.length <= 100
  • 1 <= word.length <= 100
  • Both strings consist of lowercase English letters.

Hints for Maximum Repeating Substring

  1. Hint 1

    The answer is bounded by sequence.length / word.length.

  2. Hint 2

    Try k = 1, 2, 3, … and stop when the repeated word no longer occurs.

  3. Hint 3

    Building the repeated string and using a plain substring search is fast enough here.

How to solve Maximum Repeating Substring

The property is monotone: if word repeated k times occurs, so does word repeated k-1 times. So climbing k from 1 and stopping at the first failure finds the maximum.

Approach

  1. Start with k = 0.
  2. While word repeated k + 1 times is a substring of sequence, increment k.
  3. Return k.

Why it works

Monotonicity holds because any occurrence of word^(k+1) contains an occurrence of word^k as a prefix. The loop cannot run more than sequence.length / word.length times, since the repeated string outgrows the sequence.

Complexity

  • Time — O(n²/m) in the worst case, well within the stated limits
  • Space — O(n) for the repeated string

Pitfalls

  • Counting non-overlapping occurrences of word anywhere is wrong — the copies must be consecutive.
  • Starting k at 1 and returning it unconditionally reports 1 when word never occurs.
  • Binary searching k works but is unnecessary and easy to get off by one.

Reference solution

Python

def maxRepeating(sequence: str, word: str) -> int:
    k = 0
    while word * (k + 1) in sequence:
        k += 1
    return k

Java

public static int maxRepeating(String sequence, String word) {
    int k = 0;
    StringBuilder cur = new StringBuilder(word);
    while (sequence.contains(cur.toString())) {
        k++;
        cur.append(word);
    }
    return k;
}

C++

int maxRepeating(string sequence, string word) {
    int k = 0;
    string cur = word;
    while (sequence.find(cur) != string::npos) {
        k++;
        cur += word;
    }
    return k;
}

JavaScript

var maxRepeating = function(sequence, word) {
    let k = 0;
    let cur = word;
    while (sequence.indexOf(cur) !== -1) {
        k++;
        cur += word;
    }
    return k;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings