{"id":5426,"date":"2019-08-11T14:56:58","date_gmt":"2019-08-11T21:56:58","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5426"},"modified":"2019-08-11T15:07:20","modified_gmt":"2019-08-11T22:07:20","slug":"leetcode-1156-swap-for-longest-repeated-character-substring","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-1156-swap-for-longest-repeated-character-substring\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1156. Swap For Longest Repeated Character Substring"},"content":{"rendered":"\n

Given a string text<\/code>, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.<\/p>\n\n\n\n

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

Input:<\/strong> text = \"ababa\"\nOutput:<\/strong> 3\nExplanation:<\/strong> We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is \"aaa\", which its length is 3.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> text = \"aaabaaa\"\nOutput:<\/strong> 6\nExplanation:<\/strong> Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring \"aaaaaa\", which its length is 6.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> text = \"aaabbaaa\"\nOutput:<\/strong> 4\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> text = \"aaaaa\"\nOutput:<\/strong> 5\nExplanation:<\/strong> No need to swap, longest repeated character substring is \"aaaaa\", length is 5.\n<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
Input:<\/strong> text = \"abcdef\"\nOutput:<\/strong> 1\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= text.length <= 20000<\/code><\/li>
  • text<\/code> consist of lowercase English characters only.<\/li><\/ul>\n\n\n\n
    Solution: HashTable<\/strong><\/h2>\n\n\n\n
    Pre-processing<\/p>\n\n\n\n
    1. Compute the longest repeated substring starts and ends with text[i].<\/li>
    2. Count the frequency of each letter.<\/li><\/ol>\n\n\n\n
      Main<\/p>\n\n\n\n
      1. Loop through each letter<\/li>
      2. Check the left and right letter
        • if they are the same, len = left + right
          • e.g1. “aa c aaa [b] aaaa” => len = 3 + 4 = 7<\/li><\/ul><\/li>
          • if they are not the same, len = max(left, right)  
            • e.g2. “aa [b] ccc d c”  => len = max(2, 3) = 3<\/li><\/ul><\/li><\/ul><\/li>
            • If the letter occurs more than len times, we can always find an extra one and swap it with the current letter => ++len
              • e.g.1, count[“a”] = 9 > 7, len = 7 + 1 = 8<\/li>
              • e.g.2, count[“c”] = 4 > 3, len = 3 + 1 = 4<\/li><\/ul><\/li><\/ol>\n\n\n\n
                Time complexity: O(n)
                Space complexity: O(n)<\/p>\n\n\n\n
                \n
                C++<\/h2>\n
                \n\n
                \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int maxRepOpt1(string text) {\n    int n = text.length();\n    \/\/ Length of repeted substring ends with text[i]\n    vector> len1(n, vector(26));\n    \/\/ Length of repeated substring starts with text[i]\n    vector> len2(n, vector(26));\n    vector counts(26);\n    int last = -1; \/\/ not a letter\n    int l = 0;\n    int ans = 0;\n    for (int i = 0; i < n; ++i) {\n      const int c = text[i] - 'a';\n      if (c == last) {\n        ++l;\n      } else { \n        last = c;\n        l = 1;\n      }      \n      len1[i][c] = l;\n      len2[i - l + 1][c] = l;\n      ++counts[c];\n      ans = max(ans, l);\n    }\n    \n    for (int i = 1; i < n - 1; ++i) {\n      int cl = text[i - 1] - 'a';\n      int cr = text[i + 1] - 'a';\n      int left = len1[i - 1][cl];\n      int right = len2[i + 1][cr];\n      int count = 0;      \n      if (cl != cr) {\n        \/\/ e.g. \"c aaa b cccc\" => \"b aaa ccccc\"\n        count = max(left + (counts[cl] > left ? 1 : 0), \n                    right + (counts[cr] > right ? 1 : 0));\n      } else {\n        \/\/ e.g. \"a c aaa b aaaa\" => \"b c aaaaaaaa\"\n        count = left + right;\n        if (counts[cl] > count) ++count;\n      }\n      ans = max(ans, count);\n    }\n    \n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
                Given a string text, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[82,177,4,314],"class_list":["post-5426","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-medium","tag-string","tag-substring","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5426","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=5426"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5426\/revisions"}],"predecessor-version":[{"id":5429,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5426\/revisions\/5429"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5426"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5426"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5426"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}