Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1668.html
1668. Maximum Repeating Substring (Easy)
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
andword
contains only lowercase English letters.
Related Topics:
String
Similar Questions:
Solution 1. Brute force
Note that find
takes O(N^2)
instead of O(N)
.
// OJ: https://leetcode.com/problems/maximum-repeating-substring/
// Time: O(N^3)
// Space: O(N)
class Solution {
public:
int maxRepeating(string sequence, string word) {
string f = word;
int k = 1;
for (; sequence.find(f) != string::npos; ++k, f += word);
return k - 1;
}
};
-
class Solution { public int maxRepeating(String sequence, String word) { int maxRepeating = 0; StringBuffer sb = new StringBuffer(); int k = 0; while (sb.length() <= sequence.length()) { sb.append(word); k++; if (sequence.indexOf(sb.toString()) >= 0) maxRepeating = k; } return maxRepeating; } } ############ 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; } }
-
// OJ: https://leetcode.com/problems/maximum-repeating-substring/ // Time: O(N^3) // Space: O(N) class Solution { public: int maxRepeating(string sequence, string word) { string f = word; int k = 1; for (; sequence.find(f) != string::npos; ++k, f += word); return k - 1; } };
-
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 ############ # 1668. Maximum Repeating Substring # https://leetcode.com/problems/maximum-repeating-substring/ class Solution: def maxRepeating(self, seq: str, w: str) -> int: res = 0 s = set() times = len(seq) // len(w) p = [w * i for i in range(1, times+1)] for c in p: if c not in s and c in seq: s.add(c) res += 1 return res
-
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() } }