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 <= 100
• 1 <= word.length <= 100
• sequence and word contains only lowercase English letters.

Solutions

• Java
• C++
• Python
• Go
• TypeScript
• RenderScript

• 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()
      }
  }
  
  

All Problems

All Solutions