Welcome to Subscribe On Youtube
1668. Maximum Repeating Substring
Description
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 <= 1001 <= word.length <= 100sequenceandwordcontains only lowercase English letters.
Solutions
-
class Solution { public int maxRepeating(String sequence, String word) { for (int k = sequence.length() / word.length(); k > 0; --k) { if (sequence.contains(word.repeat(k))) { return k; } } return 0; } } -
class Solution { public: int maxRepeating(string sequence, string word) { int ans = 0; string t = word; int x = sequence.size() / word.size(); for (int k = 1; k <= x; ++k) { // C++ 这里从小到大枚举重复值 if (sequence.find(t) != string::npos) { ans = k; } t += word; } return ans; } }; -
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 -
func maxRepeating(sequence string, word string) int { for k := len(sequence) / len(word); k > 0; k-- { if strings.Contains(sequence, strings.Repeat(word, k)) { return k } } return 0 } -
function maxRepeating(sequence: string, word: string): number { let n = sequence.length; let m = word.length; for (let k = Math.floor(n / m); k > 0; k--) { if (sequence.includes(word.repeat(k))) { return k; } } return 0; } -
impl Solution { pub fn max_repeating(sequence: String, word: String) -> i32 { let n = sequence.len(); let m = word.len(); if n < m { return 0; } let mut dp = vec![0; n - m + 1]; for i in 0..=n - m { let s = &sequence[i..i + m]; if s == word { dp[i] = (if (i as i32) - (m as i32) < 0 { 0 } else { dp[i - m] }) + 1; } } *dp.iter().max().unwrap() } }