{"id":7718,"date":"2020-11-28T10:22:33","date_gmt":"2020-11-28T18:22:33","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7718"},"modified":"2020-11-28T10:53:38","modified_gmt":"2020-11-28T18:53:38","slug":"leetcode-1668-maximum-repeating-substring","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/string\/leetcode-1668-maximum-repeating-substring\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1668. Maximum Repeating Substring"},"content":{"rendered":"\n

For a string sequence<\/code>, a string word<\/code> is k<\/code>-repeating<\/strong> if word<\/code> concatenated k<\/code> times is a substring of sequence<\/code>. The word<\/code>‘s maximum k<\/code>-repeating value<\/strong> is the highest value k<\/code> where word<\/code> is k<\/code>-repeating in sequence<\/code>. If word<\/code> is not a substring of sequence<\/code>, word<\/code>‘s maximum k<\/code>-repeating value is 0<\/code>.<\/p>\n\n\n\n

Given strings sequence<\/code> and word<\/code>, return the maximum k<\/code>-repeating value<\/strong> of word<\/code> in sequence<\/code><\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> sequence = \"ababc\", word = \"ab\"\nOutput:<\/strong> 2\nExplanation: <\/strong>\"abab\" is a substring in \"ababc\".\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> sequence = \"ababc\", word = \"ba\"\nOutput:<\/strong> 1\nExplanation: <\/strong>\"ba\" is a substring in \"ababc\". \"baba\" is not a substring in \"ababc\".\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> sequence = \"ababc\", word = \"ac\"\nOutput:<\/strong> 0\nExplanation: <\/strong>\"ac\" is not a substring in \"ababc\". \n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= sequence.length <= 100<\/code><\/li>
  • 1 <= word.length <= 100<\/code><\/li>
  • sequence<\/code> and word<\/code> contains only lowercase English letters.<\/li><\/ul>\n\n\n\n
    Solution: Brute Force<\/strong><\/h2>\n\n\n\n
    Time complexity: O(n^2)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    class Solution {\npublic:\n  int maxRepeating(string sequence, string word) {\n    string s(word);\n    for (int i = 1;;++i) {\n      if (sequence.find(s) == string::npos) return i - 1;\n      s += word;\n    }\n    return -1;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    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,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47],"tags":[222,4,314],"class_list":["post-7718","post","type-post","status-publish","format-standard","hentry","category-string","tag-easy","tag-string","tag-substring","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7718","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7718"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7718\/revisions"}],"predecessor-version":[{"id":7720,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7718\/revisions\/7720"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7718"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7718"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7718"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}