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.
Solution: Brute Force
Time complexity: O(n^2)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 |
class Solution { public: int maxRepeating(string sequence, string word) { string s(word); for (int i = 1;;++i) { if (sequence.find(s) == string::npos) return i - 1; s += word; } return -1; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment