Skip to content

1668. Maximum Repeating Substring

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
 public:
  int maxRepeating(string sequence, string word) {
    int ans = 1;
    string repeating = word;
    while (sequence.find(repeating) != string::npos) {
      ++ans;
      repeating += word;
    }
    return ans - 1;
  }
};

1
2
3
4
5
6
7
8
class Solution {
  public int maxRepeating(String sequence, String word) {
    int ans = 1;
    while (sequence.contains(word.repeat(ans)))
      ++ans;
    return ans - 1;
  }
}

1
2
3
4
5
6
class Solution:
  def maxRepeating(self, sequence: str, word: str) -> int:
    ans = 1
    while word * ans in sequence:
      ans += 1
    return ans - 1