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;
}
};
Java
-
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; } }
-
// 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