1668. Maximum Repeating Substring

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.

 

Example 1:

Input: sequence = "ababc", word = "ab"
Output: 2
Explanation: "abab" is a substring in "ababc".

Example 2:

Input: sequence = "ababc", word = "ba"
Output: 1
Explanation: "ba" is a substring in "ababc". "baba" is not a substring in "ababc".

Example 3:

Input: sequence = "ababc", word = "ac"
Output: 0
Explanation: "ac" is not a substring in "ababc". 

 

Constraints:

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

Rust Solution

struct Solution;

impl Solution {
    fn max_repeating(sequence: String, word: String) -> i32 {
        let n = sequence.len();
        let m = word.len();
        let mut k = n / m;
        while k > 0 {
            let mut s = "".to_string();
            for _ in 0..k {
                s += &word;
            }
            if sequence.contains(&s) {
                break;
            }
            k -= 1;
        }
        k as i32
    }
}

#[test]
fn test() {
    let sequence = "ababc".to_string();
    let word = "ab".to_string();
    let res = 2;
    assert_eq!(Solution::max_repeating(sequence, word), res);
    let sequence = "ababc".to_string();
    let word = "ba".to_string();
    let res = 1;
    assert_eq!(Solution::max_repeating(sequence, word), res);
    let sequence = "ababc".to_string();
    let word = "ac".to_string();
    let res = 0;
    assert_eq!(Solution::max_repeating(sequence, word), res);
}

Having problems with this solution? Click here to submit an issue on github.